Access Restriction

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

   Open content in new tab
Source: ACM Digital Library