Randomized algorithms for the low-rank approximation of matrices
Top Cited Papers
- 18 December 2007
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 104 (51) , 20167-20172
- https://doi.org/10.1073/pnas.0709640104
Abstract
We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application (inter alia) to the evaluation of the singular value decompositions of numerically low-rank matrices. Being probabilistic, the schemes described here have a finite probability of failure; in most cases, this probability is rather negligible (10(-17) is a typical value). In many situations, the new procedures are considerably more efficient and reliable than the classical (deterministic) ones; they also parallelize naturally. We present several numerical examples to illustrate the performance of the schemes.Keywords
This publication has 9 references indexed in Scilit:
- On interpolation and integration in finite-dimensional spaces of bounded functionsCommunications in Applied Mathematics and Computational Science, 2006
- New YorkPublished by Cambridge University Press (CUP) ,2006
- On the Compression of Low Rank MatricesSIAM Journal on Scientific Computing, 2005
- The maximal-volume concept in approximation by low-rank matricesPublished by American Mathematical Society (AMS) ,2001
- Incomplete Cross Approximation in the Mosaic-Skeleton MethodComputing, 2000
- Efficient Algorithms for Computing a Strong Rank-Revealing QR FactorizationSIAM Journal on Scientific Computing, 1996
- Efficient computation of the DFT with only a subset of input or output pointsIEEE Transactions on Signal Processing, 1993
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- Estimating Extremal Eigenvalues and Condition Numbers of MatricesSIAM Journal on Numerical Analysis, 1983