2014 ImprovingtheModifiedNyströmMeth

• (Wang et al., 2014) ⇒ Shusen Wang, Chao Zhang, Hui Qian, and Zhihua Zhang. (2014). “Improving the Modified Nyström Method Using Spectral Shifting.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623614

Subject Headings: Symmetric Positive Semidefinite Matrix.

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Improving+the+Modified+Nystr%F6m+Method+Using+Spectral+Shifting
• http://dl.acm.org/citation.cfm?id=2623330.2623614&preflayout=flat#citedby

Quotes

Author Keywords

• Kernel approximation; large-scale machine learning; numerical linear algebra; the nyströ m method

Abstract

The Nystrom method is an efficient approach to enabling large-scale kernel methods. The Nystrom method generates a fast approximation to any large-scale symmetric positive semidefinite (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nystrom approximation is low-rank, when the spectrum of the SPSD matrix decays slowly, the Nystrom approximation is of low accuracy. In this paper, we propose a variant of the Nystrom method called the modified Nystrom by spectral shifting (SS-Nystrom). The SS-Nystrom method works well no matter whether the spectrum of SPSD matrix decays fast or slow. We prove that our SS-Nystrom has a much stronger error bound than the standard and modified Nystrom methods, and that SS-Nystrom 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-Nystrom approximation can be computed nearly as efficient as the modified Nystrom approximation. Finally, our SS-Nystrom method demonstrates significant improvements over the standard and modified Nystrom methods on several real-world datasets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ImprovingtheModifiedNyströmMeth	Shusen Wang Chao Zhang Hui Qian Zhihua Zhang			Improving the Modified Nyström Method Using Spectral Shifting				10.1145/2623330.2623614		2014