Fast computation of low-rank matrix approximations

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.

REFERENCES

• 1: Alon, N., Krivelevich, M., and Vu, V. H. 2002. Concentration of eigenvalues of random matrices. Israel Math. J. 131, 259--267.
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: Peter N. Belhumeur , João P. Hespanha , David J. Kriegman, Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.7, p.711-720, July 1997 [doi>10.1109/34.598228]
• 4: Michael W. Berry , Zlatko Drmac , Elizabeth R. Jessup, Matrices, Vector Spaces, and Information Retrieval, SIAM Review, v.41 n.2, p.335-362, June 1999 [doi>10.1137/S0036144598347035]
• 5: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 6: Deerwester, S., Dumais, S., Landauer, T., Furnas, G., and Harshman, R. 1990. Indexing by latent semantic analysis. J. Soc. Inf. Sci. 41, 6, 391--407.
• 7: P. Drineas , A. Frieze , R. Kannan , S. Vempala , V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, v.56 n.1-3, p.9-33 [doi>10.1023/B:MACH.0000033113.59016.96]
• 8: Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast monte-carlo algorithms for finding low-rank approximations, Journal of the ACM (JACM), v.51 n.6, p.1025-1041, November 2004 [doi>10.1145/1039488.1039494]
• 10: Füredi, Z., and Komlós, J. 1981. The eigenvalues of random symmetric matrices. Combinatorica 1, 3, 233--241.
• 11: Athinodoros S. Georghiades , Peter N. Belhumeur , David J. Kriegman, From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.6, p.643-660, June 2001 [doi>10.1109/34.927464]
• 12: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 13: Christos H. Papadimitriou , Prabhakar Raghavan , Hisao Tamaki , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Journal of Computer and System Sciences, v.61 n.2, p.217-235, Oct. 2000 [doi>10.1006/jcss.2000.1711]
• 14: V. H. Vu, Spectral norm of random matrices, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060654]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory

Keywords:
Singular value decomposition, low rank approximation, sampling