Improving the Modified Nyström Method Using Spectral Shifting
Oct 8, 2014 1533 views 
The Nyström method is an efficient approach to enabling large-scale kernel methods. The Nyström method generates a fast approximation to any large-scale symmetric positive semidefinete (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nyström approximation is low-rank, when the spectrum of the SPSD matrix decays slowly, the Nyström approximation is of low accuracy. In this paper, we propose a variant of the Nyström method called the modified Nyström by spectral shifting (SS-Nyström). The SS-Nyström method works well no matter whether the spectrum of SPSD matrix decays fast or slow. We prove that our SS-Nyström has a much stronger error bound than the standard and modified Nyström methods, and that SS-Nyström can be even more accurate than the truncated SVD of the same scale in some cases. We also devise an algorithm such that the SS-Nyström approximation can be computed nearly as efficient as the modified Nyström approximation. Finally, our SS-Nyström method demonstrates significant improvements over the standard and modified Nyström methods on several real-world datasets.