Fast monte-carlo algorithms for finding low-rank approximations.

We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for...

Ausführliche Beschreibung

Bibliographische Detailangaben

Veröffentlicht in:	Journal of the ACM 51, 6 (2004).
1. Verfasser:	Frieze, Alan
Format:	Artikel
Sprache:	English
Schlagworte:	Theory of computation. Analysis of algorithms and problem complexity. Mathematics of computing. Numerical analysis. Numerical linear algebra. Information systems. Information storage and retrieval. Algorithms. Theory.