Density-weighted Nyström method for computing large kernel eigensystems.
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.
Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong. twinsen@cse.ust.hk
Kai
K
Zhang
James T
JT
Kwok
D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003198:Computer Simulation; D006801:Humans; D007858:Learning / Q000502:physiology*; D016571:Neural Networks, Computer; D010363:Pattern Recognition, Automated / Q000379:methods*