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