Density-Weighted Nyström Method for Computing Large Kernel Eigensystems
Open Access
- 1 January 2009
- journal article
- Published by MIT Press in Neural Computation
- Vol. 21 (1), 121-146
- https://doi.org/10.1162/neco.2009.11-07-651
Abstract
The Nyström method is a well-known sampling-based technique for approximating the eigensystem of large kernel matrices. However, the chosen samples in the Nyström method are all assumed to be of equal importance, which deviates from the integral equation that defines the kernel eigenfunctions. Motivated by this observation, we extend the Nyström method to a more general, density-weighted version. We show that by introducing the probability density function as a natural weighting scheme, the approximation of the eigensystem can be greatly improved. An efficient algorithm is proposed to enforce such weighting in practice, which has the same complexity as the original Nyström method and hence is notably cheaper than several other alternatives. Experiments on kernel principal component analysis, spectral clustering, and image segmentation demonstrate the encouraging performance of our algorithm.Keywords
This publication has 12 references indexed in Scilit:
- Spectral grouping using the nystrom methodIeee Transactions On Pattern Analysis and Machine Intelligence, 2004
- An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value DecompositionLecture Notes in Computer Science, 2003
- Kernels and Regularization on GraphsLecture Notes in Computer Science, 2003
- An efficient k-means clustering algorithm: analysis and implementationIeee Transactions On Pattern Analysis and Machine Intelligence, 2002
- Normalized cuts and image segmentationIeee Transactions On Pattern Analysis and Machine Intelligence, 2000
- Accelerating exactk-means algorithms with geometric reasoningPublished by Association for Computing Machinery (ACM) ,1999
- Nonlinear Component Analysis as a Kernel Eigenvalue ProblemNeural Computation, 1998
- FastMapPublished by Association for Computing Machinery (ACM) ,1995
- Vector Quantization and Signal CompressionPublished by Springer Science and Business Media LLC ,1992
- Optimal algorithms for approximate clusteringPublished by Association for Computing Machinery (ACM) ,1988