Large-scale eigenvector approximation via Hilbert Space Embedding Nyström

• A new criterion for Nystrom method to find accurate eigenvector approximation.
• The conventional criterion does not work well in eigenvector approximation.
• We need to adjust kernel width together with average weight adaptively.
• Propose a new criterion to adaptively optimize the parameters efficiently.

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.