Large-scale eigenvector approximation via Hilbert Space Embedding Nystrom

摘要

The Nystrom 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 Nystrom, it is no longer true. This unexpected discovery opens a question: What criterion should we use in Nystrom to generate a decent eigenvector approximation? To address this problem, we propose a novel criterion named Hilbert Space Embedding (HSE) Nystrom 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 Nystrom methods with the proposed criterion, including K-means Nystrom and Density Nystrom. 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. (C) 2014 Elsevier Ltd. All rights reserved.