A Randomized Algorithm for Principal Component Analysis
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 31 (3), 1100-1124
- https://doi.org/10.1137/080736417
Abstract
Principal component analysis (PCA) requires the computation of a low-rank approximation to a matrix containing the data being analyzed. In many applications of PCA, the best possible accuracy of any rank-deficient approximation is at most a few digits (measured in the spectral norm, relative to the spectral norm of the matrix being approximated). In such circumstances, efficient algorithms have not come with guarantees of good accuracy, unless one or both dimensions of the matrix being approximated are small. We describe an efficient algorithm for the low-rank approximation of matrices that produces accuracy that is very close to the best possible accuracy, for matrices of arbitrary sizes. We illustrate our theoretical results via several numerical examples.Keywords
Other Versions
This publication has 21 references indexed in Scilit:
- Relative-Error $CUR$ Matrix DecompositionsSIAM Journal on Matrix Analysis and Applications, 2008
- Fast computation of low-rank matrix approximationsJournal of the ACM, 2007
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix DecompositionSIAM Journal on Computing, 2006
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a MatrixSIAM Journal on Computing, 2006
- Condition Numbers of Gaussian Random MatricesSIAM Journal on Matrix Analysis and Applications, 2005
- Fast monte-carlo algorithms for finding low-rank approximationsJournal of the ACM, 2004
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- Some Applications of the Rank Revealing QR FactorizationSIAM Journal on Scientific and Statistical Computing, 1992
- Indexing by latent semantic analysisJournal of the American Society for Information Science, 1990
- Estimating Extremal Eigenvalues and Condition Numbers of MatricesSIAM Journal on Numerical Analysis, 1983