Improved Bounds for the Nyström Method With Application to Kernel Classification
Improved Bounds for the Nyström Method With Application to Kernel Classification
We develop two approaches for analyzing the approximation error bound for the Nystr\"{o}m method, one based on the concentration inequality of integral operator, and one based on the compressive sensing theory. We show that the approximation error, measured in the spectral norm, can be improved from $O(N/\sqrt{m})$ to $O(N/m^{1 - …