Fast monte-carlo algorithms for finding low-rank approximations
- 1 November 2004
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 51 (6), 1025-1041
- https://doi.org/10.1145/1039488.1039494
Abstract
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 some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D * of rank at most k so that holds with probability at least 1 − δ (where |·| F is the Frobenius norm). The algorithm takes time polynomial in k ,1/ϵ, log(1/δ) only and is independent of m and n . In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.Keywords
This publication has 10 references indexed in Scilit:
- Clustering Large Graphs via the Singular Value DecompositionMachine Learning, 2004
- Fast computation of low rank matrix approximationsPublished by Association for Computing Machinery (ACM) ,2001
- Latent Semantic Indexing: A Probabilistic AnalysisJournal of Computer and System Sciences, 2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- A Simple Algorithm for Constructing Szemerédi's Regularity PartitionThe Electronic Journal of Combinatorics, 1999
- Using Linear Algebra for Intelligent Information RetrievalSIAM Review, 1995
- The Algorithmic Aspects of the Regularity LemmaJournal of Algorithms, 1994
- Improving the retrieval of information from external sourcesBehavior Research Methods, Instruments & Computers, 1991
- Indexing by latent semantic analysisJournal of the American Society for Information Science, 1990