On sampling-based approximate spectral decomposition

ABSTRACT

This paper addresses the problem of approximate singular value decomposition of large dense matrices that arises naturally in many machine learning applications. We discuss two recently introduced sampling-based spectral decomposition techniques: the Nyström and the Column-sampling methods. We present a theoretical comparison between the two methods and provide novel insights regarding their suitability for various applications. We then provide experimental results motivated by this theory. Finally, we propose an efficient adaptive sampling technique to select informative columns from the original matrix. This novel technique outperforms standard sampling methods on a variety of datasets.

REFERENCES

• 1: Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109681]
• 2: Petros Drineas , Michael W. Mahoney, On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning, The Journal of Machine Learning Research, 6, p.2153-2175, 12/1/2005
• 3: Charless Fowlkes , Serge Belongie , Fan Chung , Jitendra Malik, Spectral Grouping Using the Nyström Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.214-225, January 2004 [doi>10.1109/TPAMI.2004.1262185]
• 4: 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
• 5: Kumar, S., Mohri, M., & Talwalkar, A. (2009). Sampling techniques for the Nyströöm method. Conf on Artificial Intelligence and Statistics (pp. 304--311).
• 6: LeCun, Y., & Cortes, C. (2009). The MNIST database of handwritten digits.
• 7: Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001). On spectral clustering: analysis and an algorithm. Neural Info. Proc. Systems (pp. 849--856).
• 8: Platt, J. C. (2004). Fast embedding of sparse similarity graphs. Neural Info. Proc. Systems (pp. 571--578).
• 9: Terence Sim , Simon Baker , Maan Bsat, The CMU Pose, Illumination, and Expression (PIE) Database, Proceedings of the Fifth IEEE International Conference on Automatic Face and Gesture Recognition, p.53, May 20-21, 2002
• 10: Talwalkar, A., Kumar, S., & Rowley, H. (2008). Large-scale manifold learning. Conference on Vision and Pattern Recognition (pp. 1--8).
• 11: Williams, C. K. I., & Seeger, M. (2000). Using the Nyströöm method to speed up kernel machines. Neural Info. Proc. Systems (pp. 682--688).
• 12: Kai Zhang , Ivor W. Tsang , James T. Kwok, Improved Nyström low-rank approximation and error analysis, Proceedings of the 25th international conference on Machine learning, p.1232-1239, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390311]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Domain decomposition methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition
      G.1.8 Partial Differential Equations
          Subjects: Spectral methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory