%0 Journal Article %1 rokhlin2009randomized %A Rokhlin, V. %A Szlam, A. %A Tygert, M. %D 2009 %I Society for Industrial and Applied Mathematics %J SIAM Journal on Matrix Analysis and Applications %K algorithm low_rank_approximation pca perturbation randomized singular_value_decomposition %N 3 %P 1100--1124 %R 10.1137/080736417 %T A Randomized Algorithm for Principal Component Analysis %V 31 %X 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.

@article{rokhlin2009randomized, 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.}, added-at = {2011-04-06T02:30:51.000+0200}, author = {Rokhlin, V. and Szlam, A. and Tygert, M.}, biburl = {https://www.bibsonomy.org/bibtex/28955f4da6e590506f82eded3f090c940/ytyoun}, doi = {10.1137/080736417}, interhash = {8fce6fe7771216d82d2067a7686bfe8d}, intrahash = {8955f4da6e590506f82eded3f090c940}, issn = {0895-4798}, journal = {SIAM Journal on Matrix Analysis and Applications}, keywords = {algorithm low_rank_approximation pca perturbation randomized singular_value_decomposition}, number = 3, pages = {1100--1124}, publisher = {Society for Industrial and Applied Mathematics}, timestamp = {2016-04-18T07:22:51.000+0200}, title = {A Randomized Algorithm for Principal Component Analysis}, volume = 31, year = 2009 }