Logo image
Back
Improved Bounds for the Nystrom Method With Application to Kernel Classification
Journal article   Open access   Peer reviewed

Improved Bounds for the Nystrom Method With Application to Kernel Classification

Rong Jin, Tianbao Yang, Mehrdad Mahdavi, Yu-Feng Li and Zhi-Hua Zhou
IEEE transactions on information theory, Vol.59(10), pp.6939-6949
10/01/2013
DOI: 10.1109/TIT.2013.2271378
url
https://arxiv.org/pdf/1111.2262View
Open Access

Abstract

We develop two approaches for analyzing the approximation error bound for the Nystrom method that approximates a positive semidefinite (PSD) matrix by sampling a small set of columns, one based on a concentration inequality for integral operators, and one based on random matrix theory. We show that the approximation error, measured in the spectral norm, can be improved from O(N/root m) to O(N/m(1-rho)) in the case of large eigengap, where N is the total number of data points, m is the number of sampled data points, and rho is an element of (0, 1/2) is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a p-power law, our analysis based on random matrix theory further improves the bound to O(N/m(p-1))under an incoherence assumption. We present a kernel classification approach based on the Nystrom method and derive its generalization performance using the improved bound. We show that when the eigenvalues of the kernel matrix follow a p-power law, we can reduce the number of support vectors to N-2p/(p(2)-1), which is sublinear in N when p > 1 + root 2, without seriously sacrificing its generalization performance.
 Computer Science Computer Science, Information Systems Engineering Engineering, Electrical & Electronic Science & Technology Technology

Details

Metrics

9 Record Views
36 Times Cited - Web of Science
Logo image