### Fast computation of low-rank matrix approximationsFast computation of low-rank matrix approximations

Access Restriction
Subscribed

 Author Achlioptas, Dimitris ♦ Mcsherry, Frank Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Singular value decomposition ♦ Low rank approximation ♦ Sampling Abstract Given a matrix $\textit{A},$ it is often desirable to find a good approximation to $\textit{A}$ that has low rank. We introduce a simple technique for accelerating the computation of such approximations when $\textit{A}$ has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to $\textit{A}.$ Our technique amounts to independently sampling and/or quantizing the entries of $\textit{A},$ thus speeding up computation by reducing the number of nonzero entries and/or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix $\textit{N}$ to $\textit{A},$ whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, $\textit{N}$ has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to $\textit{A}$ + $\textit{N}$ is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm. 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 2007-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 54 Issue Number 2

#### Open content in new tab

Source: ACM Digital Library