Fast monte-carlo algorithms for finding low-rank approximations

ABSTRACT

We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k, which is smaller than m and 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 k so that holds with probability at least 1 − δ (where |·|_F is the Frobenius norm). The algorithm takes time polynomial in 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.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 3: Ziv Bar-Yossef, Sampling lower bounds via information theory, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780593]
• 4: 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]
• 5: Deerwester, S., Dumais, S. T., Landauer, T. K., Furnas, G. W., and Harshman, R. A. 1990. Indexing by latent semantic analysis. J. Soc. Inf. Sci. 41, 6, 391--407.
• 6: P. Drineas , R. Kannan, Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.452, October 14-17, 2001
• 7: 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
• 8: 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]
• 9: Drineas, P., Mahoney, M. W., and Kannan, R. 2004b. Fast monte carlo algorithms for matrices II: Computing low-rank approximations to a matrix. Tech. Rep. Yale University, YALEU/DCS/TR-1270, 2004.
• 10: Dumais, S. T. 1991. Improving the retrieval of information from external sources. Behav. Res. Meth. Instrum. Comput. 23, 2, 229--236.
• 11: S. T. Dumais , G. W. Furnas , T. K. Landauer , S. Deerwester , R. Harshman, Using latent semantic analysis to improve access to textual information, Proceedings of the SIGCHI conference on Human factors in computing systems, p.281-285, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57214]
• 12: A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
• 13: Frieze, A. M., and Kannan, R. 1999a. Quick approximations to matrices and applications. Combinatorica 19, 175--220.
• 14: Frieze, A. M., and Kannan, R. 1999b. A simple algorithm for constructing Szemeredi's Regularity Partition. Elect. J. Combinat. 6, 1, R17.
• 15: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 16: Golub, G. H., and Van Loan, C. F. 1989. Matrix Computations, Johns Hopkins University Press, London, England.
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 18: Komlós, J., and Simonovits, M. 1996. Szemerédi's Regularity Lemma and its applications in graph theory. Combinatorics, Paul Erdos is Eighty, Bolyai Society Mathematical Studies, D. Miklos et al. Eds. 2, 295--352.
• 19: 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]
• 20: Szemeredi, E. 1978. Regular partitions of graphs. Proceedings, Colloque Inter. CNRS, J.-C. Bermond, J.-C. Fournier, M. Las Vergnas and D. Sotteau, Eds. 399--401.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Theory

Keywords:
Matrix algorithms, low-rank approximation, sampling