标题： 一种改进的Nystrom方法对于大特征值间隙的界限 显示英文标题

标题： An Improved Bound for the Nystrom Method for Large Eigengap

摘要： 我们在核矩阵谱中存在大特征值间隔的假设下，为Nyström方法的近似误差开发了一个改进的界限。 这是基于经验观察，即特征值间隔对Nyström方法的近似误差有显著影响。 我们的方法基于积分算子的集中不等式和矩阵扰动理论。 我们的分析表明，当存在大特征值间隔时，在Frobenius范数下，我们可以将Nyström方法的近似误差从$O(N/m^{1/4})$改进到$O(N/m^{1/2})$，其中$N$是核矩阵的大小，$m$是采样列的数量。 显示英文摘要

摘要： 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/m^{1/4})$ to $O(N/m^{1/2})$ when measured in Frobenius norm, where $N$ is the size of the kernel matrix, and $m$ is the number of sampled columns.