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...

Full description

Bibliographic Details

Published in:	Journal of the ACM 51, 6 (2004).
Main Author:	Frieze, Alan
Format:	Article
Language:	English
Subjects:	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.