Improved Nystrom low rank approximation and error analysis

Publisher:
Omnipress
Publication Type:
Conference Proceeding
Citation:
Proceedings of the 25 th International Conference on Machine Learning, 2008, pp. 1232 - 1239
Issue Date:
2008-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013004296OK.pdf558.05 kB
Adobe PDF
Low-rank matrix approximation is an effective tool in alleviating the memory and computational burdens of kernel methods and sampling, as the mainstream of such algorithms, has drawn considerable attention in both theory and practice. This paper presents detailed studies on the Nystr¨om sampling scheme and in particular, an error analysis that directly relates the Nystr¨om approximation quality with the encoding powers of the landmark points in summarizing the data. The resultant error bound suggests a simple and efficient sampling scheme, the k-means clustering algorithm, for Nystr¨om low-rank approximation. We compare it with state-of-the-art approaches that range from greedy schemes to probabilistic sampling. Our algorithm achieves significant performance gains in a number of supervised/ unsupervised learning tasks including kernel PCA and least squares SVM.
Please use this identifier to cite or link to this item: