Access Restriction

Author Frieze, Alan ♦ Kannan, Ravi ♦ Vempala, Santosh
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Matrix algorithms ♦ Low-rank approximation ♦ Sampling
Abstract We consider the problem of approximating a given $\textit{m}$ × $\textit{n}$ matrix $\textbf{A}$ by another matrix of specified rank $\textit{k},$ which is smaller than $\textit{m}$ and $\textit{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 $\textit{k}$ so that holds with probability at least 1 ™ Δ (where $|·|_{F}$ is the Frobenius norm). The algorithm takes time polynomial in $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 51
Issue Number 6
Page Count 17
Starting Page 1025
Ending Page 1041

Open content in new tab

   Open content in new tab
Source: ACM Digital Library