Towards Large Scale Spectral Problems via Diffusion Process

Abstract

© 2017 IEEE. Spectral methods refer to the problem of finding eigenvectors of an affinity matrix. Despite promising performance on revealing manifold structure, they are limited in its applicability to large-scale problems due to the high computational cost of eigendecomposition. Nyström method, as a classic method, seeks an approximate solution by first solving a smaller eigenproblem defined on a subset of landmarks, and then extrapolating the eigenvectors of all points through the linear combinations of landmarks. In this paper, we embed a simple yet effective diffusion process into Nyström formula so that we can utilize all data points rather than only landmarks to set up the reduced eigenproblem and estimate the out-of-sample embedding. We apply our method on both dimension reduction and spectral clustering problems. Extensive experiments show that the proposed method can reduce the approximation error with fewer landmarks and less run time.