TY - GEN
T1 - Low rank approximation using error correcting coding matrices
AU - Ubaru, Shashanka
AU - Mazumdar, Arya
AU - Saad, Yousef
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Low-rank matrix approximation is an integral component of tools such as principal component analysis (PCA), as well as is an important instrument used in applications like web search, text mining and computer vision, e.g., face recognition. Recently, randomized algorithms were proposed to effectively construct low rank approximations of large matrices. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations. The benefits of using these code matrices are the following: (i) They are easy to generate and they reduce randomness significantly, (ii) Code matrices have low coherence and have a better chance of preserving the geometry of an entire subspace of vectors; (iii) Unlike Fourier transforms or Hadamard matrices, which require sampling O(Hogfc) columns for a rank-fc approximation, the log factor is not necessary in the case of code matrices, (iv) Under certain conditions, the approximation errors can be better and the singular values obtained can be more accurate, than those obtained using Gaussian random matrices and other structured random matrices.
AB - Low-rank matrix approximation is an integral component of tools such as principal component analysis (PCA), as well as is an important instrument used in applications like web search, text mining and computer vision, e.g., face recognition. Recently, randomized algorithms were proposed to effectively construct low rank approximations of large matrices. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations. The benefits of using these code matrices are the following: (i) They are easy to generate and they reduce randomness significantly, (ii) Code matrices have low coherence and have a better chance of preserving the geometry of an entire subspace of vectors; (iii) Unlike Fourier transforms or Hadamard matrices, which require sampling O(Hogfc) columns for a rank-fc approximation, the log factor is not necessary in the case of code matrices, (iv) Under certain conditions, the approximation errors can be better and the singular values obtained can be more accurate, than those obtained using Gaussian random matrices and other structured random matrices.
UR - http://www.scopus.com/inward/record.url?scp=84969512926&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969512926&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84969512926
T3 - 32nd International Conference on Machine Learning, ICML 2015
SP - 702
EP - 710
BT - 32nd International Conference on Machine Learning, ICML 2015
A2 - Bach, Francis
A2 - Blei, David
PB - International Machine Learning Society (IMLS)
T2 - 32nd International Conference on Machine Learning, ICML 2015
Y2 - 6 July 2015 through 11 July 2015
ER -