An Improved Bound for the Nyström Method for Large Eigengap

We develop an improved bound for the ap-proximation error of the Nyströ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öm method. Our approach is based on the con-centration inequality of integral operator and the theory of matrix perturbation. Our anal-ysis shows that when there is a large eigen-gap, we can improve the approximation er-ror of the Nyström method from O(N/m1/4) to O(N/m1/2) when measured in Frobenius norm, where N is the size of the kernel matrix, and m is the number of sampled columns. 1