Block-quantized kernel matrix for fast spectral embedding

ABSTRACT

Eigendecomposition of kernel matrix is an indispensable procedure in many learning and vision tasks. However, the cubic complexity O(N³) is impractical for large problem, where N is the data size. In this paper, we propose an efficient approach to solve the eigendecomposition of the kernel matrix W. The idea is to approximate W with W that is composed of m² constant blocks. The eigenvectors of W, which can be solved in O(m³) time, is then used to recover the eigenvectors of the original kernel matrix. The complexity of our method is only O(mN + m³), which scales more favorably than state-of-the-art low rank approximation and sampling based approaches (O(m²N + m³)), and the approximation quality can be controlled conveniently. Our method demonstrates encouraging scaling behaviors in experiments of image segmentation (by spectral clustering) and kernel principal component analysis.

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: Baker, C. (1977). The numerical treatment of integral equations. Oxford: Clarendon Press.
• 4: Bhatia, R. (1997). Matrix analysis. New York: Springer-Verlag.
• 5: Timothee Cour , Florence Benezit , Jianbo Shi, Spectral Segmentation with Multiscale Graph Decomposition, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.1124-1131, June 20-26, 2005 [doi>10.1109/CVPR.2005.332]
• 6: Drineas, P., & Mahoney, M. W. (2005). On the nyströöm method for approximating a Gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6, 2153--2175.
• 7: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 8: Shai Fine , Katya Scheinberg, Efficient svm training using low-rank kernel representations, The Journal of Machine Learning Research, 2, 3/1/2002
• 9: 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]
• 10: 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.
• 11: Andrew W. Moore, Very fast EM-based mixture model clustering using multiresolution kd-trees, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.543-549, July 1999
• 12: Ouimet, M., & Bengio, Y. (2005). Greedy spectral embedding. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 253--260).
• 13: 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]
• 14: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 15: Smola, A. J., & Bartlett, P. L. (2000). Sparse greedy Gaussian process regression. Advances in Neural Information Processing System (pp. 619--625).
• 16: 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
• 17: Williams, C., & Seeger, M. (2001). Using the Nyströöm method to speed up kernel machines. Advances in Neural Information Processing Systems. (pp. 682--688).

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Theory