Improved Nyström low-rank approximation and error analysis

ABSTRACT

Low-rank matrix approximation is an effective tool in alleviating the memory and computational burdens of kernel methods and sampling, as the mainstream of such algorithms, has drawn considerable attention in both theory and practice. This paper presents detailed studies on the Nyström sampling scheme and in particular, an error analysis that directly relates the Nyström approximation quality with the encoding powers of the landmark points in summarizing the data. The resultant error bound suggests a simple and efficient sampling scheme, the k-means clustering algorithm, for Nyström low-rank approximation. We compare it with state-of-the-art approaches that range from greedy schemes to probabilistic sampling. Our algorithm achieves significant performance gains in a number of supervised/unsupervised learning tasks including kernel PCA and least squares SVM.

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: Francis R. Bach , Michael I. Jordan, Kernel independent component analysis, The Journal of Machine Learning Research, 3, p.1-48, 3/1/2003
• 3: Francis R. Bach , Michael I. Jordan, Predictive low-rank decomposition for kernel methods, Proceedings of the 22nd international conference on Machine learning, p.33-40, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102356]
• 4: Baker, C. (1977). The numerical treatment of integral equations. Oxford: Clarendon Press.
• 5: Belkin, M., & Niyogi, P. (2002). Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems 14.
• 6: Drineas, P., Drinea, E., & Huggins, P. (2003). An experimental evaluation of a Monte-Carlo algorithm for singular value decomposition. Proceedings of 8th Panhellenic Conference on Informatics (pp. 279--296).
• 7: 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
• 8: Elkan, E. (2003). Using the triangular inequality to accelerate k-means. Proceedings of the 21th International Conference on Machine Learning (pp. 147--153).
• 9: Shai Fine , Katya Scheinberg, Efficient svm training using low-rank kernel representations, The Journal of Machine Learning Research, 2, 3/1/2002
• 10: 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]
• 11: 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
• 12: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 13: Golub, G., & Van Loan, C. (1996). Matrix computations. Johns Hopkins University Press. 3rd edition.
• 14: Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002 [doi>10.1109/TPAMI.2002.1017616]
• 15: Lawrence, N. Seeger, M., & Herbrich, R. (2003). Fast sparse Gaussian process methods: The informative vector machine. Advances in Neural Information Processing Systems. (pp. 625--632). MIT Press.
• 16: Ouimet, M., & Bengio, Y. (2005). Greedy spectral embedding. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 253--260).
• 17: Platt, J. C. (2005). Fastmap, MetricMap, and Landmark MDS are all Nyström algorithms. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 261--268).
• 18: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 19: Alex J. Smola , Bernhard Schökopf, Sparse Greedy Matrix Approximation for Machine Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.911-918, June 29-July 02, 2000
• 20: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 21: Christopher K. I. Williams , Matthias Seeger, The Effect of the Input Density Distribution on Kernel-based Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.1159-1166, June 29-July 02, 2000
• 22: Williams, C., & Seeger, M. (2001). Using the Nyströöm method to speed up kernel machines. Advances in Neural Information Processing Systems 13 (pp. 682--688).
• 23: Kai Zhang , James T. Kwok, Block-quantized kernel matrix for fast spectral embedding, Proceedings of the 23rd international conference on Machine learning, p.1097-1104, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143982]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory