An Improved Bound for the Nystrom Method for Large Eigengap

We develop an improved bound for the approximation error of the Nystr"{o}m method under the assumption that there is a large eigengap in the spectrum of kernel matrix. This is based on the empirical observation that the eigengap has a significant impact on the approximation error of the Nystr"{o}m method. Our approach is based on the concentration inequality of integral operator and the theory of matrix perturbation. Our analysis shows that when there is a large eigengap, we can improve the approximation error of the Nystr"{o}m method from $O(N\mathrm{/}{m}^{1\mathrm{/}4})$ to $O(N\mathrm{/}{m}^{1\mathrm{/}2})$ when measured in Frobenius norm, where $N$ is the size of the kernel matrix, and $m$ is the number of sampled columns.