Randomized algorithms for the low-rank approximation of matrices
-
- Edo Liberty
- Department of Computer Science and
-
- Franco Woolfe
- Program in Applied Math, Yale University, 51 Prospect Street, New Haven, CT 06511; and
-
- Per-Gunnar Martinsson
- Department of Applied Math, University of Colorado, 526 UCB, Boulder, CO 80309-0526
-
- Vladimir Rokhlin
- Department of Computer Science and
-
- Mark Tygert
- Program in Applied Math, Yale University, 51 Prospect Street, New Haven, CT 06511; and
Description
<jats:p>We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application (<jats:italic>inter alia</jats:italic>) 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<jats:sup>−17</jats:sup>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.</jats:p>
Journal
-
- Proceedings of the National Academy of Sciences
-
Proceedings of the National Academy of Sciences 104 (51), 20167-20172, 2007-12-18
Proceedings of the National Academy of Sciences
- Tweet
Details 詳細情報について
-
- CRID
- 1360283692106525568
-
- ISSN
- 10916490
- 00278424
-
- Data Source
-
- Crossref
- KAKEN