×

Large-scale eigenvector approximation via Hilbert space embedding Nyström. (English) Zbl 1374.68400

Summary: The Nyström method approximates eigenvectors of a given kernel matrix by randomly sampling subset of data. Previous researches focus on good kernel approximation while the quality of eigenvector approximation is rarely explored. In online eigenvector approximation method, one can minimize the kernel approximation error to guarantee a good eigenvector approximation. However in this work, we paradoxically prove that for batch approximation methods like Nyström, it is no longer true. This unexpected discovery opens a question: What criterion should we use in Nyström to generate a decent eigenvector approximation? To address this problem, we propose a novel criterion named Hilbert Space Embedding (HSE) Nyström criterion which directly minimizes the eigenvector approximation error. The proposed HSE criterion provides a general framework to approximate eigenvectors within linear time and space complexity. We then show that we can rediscover many successful Nyström methods with the proposed criterion, including K-means Nyström and Density Nyström. To further demonstrate the power of our criterion, we actually design a novel algorithm to approximate eigenvectors of Laplacian matrices based on the proposed criterion with better accuracy among existing linear complexity methods. We demonstrate the efficiency and efficacy of our proposal in numerical experiments.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 1373-1396 (2003) · Zbl 1085.68119
[6] Fowlkes, C.; Belongie, S.; Chung, F.; Malik, J., Spectral grouping using the Nystrom method, IEEE Trans. Pattern Anal. Mach. Intell., 26, 214-225 (2004)
[7] Nyström, E., Über die praktische auflösung von integralgleichungen mit anwendungen auf randwertaufgaben, Acta Math., 54, 185-204 (1930) · JFM 56.0342.01
[9] Drineas, P.; Mahoney, M., On the Nyström method for approximating a gram matrix for improved kernel-based learning, J. Mach. Learn. Res., 6, 2175 (2005) · Zbl 1222.68186
[16] Bengio, Y.; Delalleau, O.; Roux, N.; Paiement, J.; Vincent, P.; Ouimet, M., Learning eigenfunctions links spectral embedding and kernel PCA, Neural Comput., 16, 2197-2219 (2004) · Zbl 1085.68120
[17] Chatelin, F., The spectral approximation of linear operators with applications to the computation of eigenelements of differential and integral operators, SIAM Rev., 23, 495-522 (1981) · Zbl 0472.65048
[19] Sriperumbudur, B.; Gretton, A.; Fukumizu, K.; Schölkopf, B.; Lanckriet, G., Hilbert Space Embeddings and metrics on probability measures, J. Mach. Learn. Res., 11, 1517-1561 (2010) · Zbl 1242.60005
[21] Zhang, K.; Kwok, J., Density-weighted Nyström method for computing large kernel eigensystems, Neural Comput., 21, 121-146 (2009) · Zbl 1178.68480
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.