%0 Journal Article %1 DBLP:journals/jacm/AchlioptasM07 %A Achlioptas, Dimitris %A McSherry, Frank %D 2007 %J J. ACM %K low_rank_approximation perturbation random_matrix singular_value_decomposition sparsification %N 2 %R 10.1145/1219092.1219097 %T Fast computation of low-rank matrix approximations %V 54 %X Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when 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 A. Our technique amounts to independently sampling and/or quantizing the entries of 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 N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A + N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm.

@article{DBLP:journals/jacm/AchlioptasM07, abstract = {Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when 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 A. Our technique amounts to independently sampling and/or quantizing the entries of 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 N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A + N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm.}, added-at = {2010-04-29T15:45:56.000+0200}, author = {Achlioptas, Dimitris and McSherry, Frank}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2d31a5d48a43050042e6c7f3bbb39b494/ytyoun}, doi = {10.1145/1219092.1219097}, interhash = {8f2e2b290a3a1424c82eda3add3c7c2b}, intrahash = {d31a5d48a43050042e6c7f3bbb39b494}, journal = {J. ACM}, keywords = {low_rank_approximation perturbation random_matrix singular_value_decomposition sparsification}, number = 2, timestamp = {2011-04-23T21:11:13.000+0200}, title = {Fast computation of low-rank matrix approximations}, volume = 54, year = 2007 }