Randomized algorithms for the low-rank approximation of matrices.
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.
Department of Computer Science and Program in Applied Math, Yale University, 51 Prospect Street, New Haven, CT 06511, USA.
Edo
E
Liberty
Franco
F
Woolfe
Per-Gunnar
PG
Martinsson
Vladimir
V
Rokhlin
Mark
M
Tygert