### Fast monte-carlo algorithms for finding low-rank approximationsFast monte-carlo algorithms for finding low-rank approximations

Access Restriction
Subscribed

 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

Source: ACM Digital Library