提高 Nyström 方法在低秩近似中的精度
本文首次提出一种核 Nystr"om 逼近算法,它在所有核矩阵中都具有可证明的准确性,且其运行时间与训练点数成线性关系,并利用快速递归采样方案,实现了基于支撑点的快速采样,相较于常用技术如均匀采样 Nystr"om 逼近和随机 Fourier 特征方法,找到更精确、低秩的核逼近方法的速度更快。
May, 2016
本文探讨标准 Nystrom 方法在排名降低方面存在的缺点,提出了一种修改方法以改进 Nystrom 逼近的固定排名。通过理论分析和数值实验来证明修改方法优于标准 Nystrom 方法,在很多情况下具有极高的精度,是最优的,并与标准 Nystrom 方法具有几乎相同的计算复杂度。
Aug, 2017
该论文对一种适用于一般矩阵的 Nystr {"o} m 方法进行了研究,并表明它的近似质量接近其他竞争方法,在数值稳定性方面表现良好。文中阐述了该方法的计算成本,并演示了可以在更新和降低矩阵时使用该方法。
Sep, 2020
本文提出了更准确的基于列 / 行采样算法的 CUR 和 Nyström 算法,其期望相对误差较小,时间复杂度低且可以避免在 RAM 中存储整个数据矩阵,并对标准 Nyström 方法和 ensemble Nyström 方法的误差下限进行了理论分析,从而建立了一个更广泛的误差界限。
Mar, 2013
本篇研究论文旨在重新考虑随机算法用于对称半正定矩阵的低秩逼近,通过实证评估了样本抽样和投影方法的性能质量和运行时间,证明了它们的互补性,在相对误差较低前提下表明了不同采样方法之间的重要区别,并为随机抽样和随机投影方法提供最坏情况的理论边界。
Mar, 2013
介绍了如何使用 Nyström 方法来寻找一般矩阵的奇异值分解和方阵的特征值分解,从而得到压缩版本的矩阵,并在选择 A_M 方面提出了一个好的初始采样算法,适用于一般矩阵和核矩阵。
May, 2013
通过将线性 k - 均值聚类应用于使用称为等级限制的 Nyström 近似构造的 {k/epsilon}(1+o (1)) 特征,本文分析了该范例应用于核 k - 均值聚类,并表明相对于不使用 Nyström 方法提供的保证,计算出的群集分配会满足相对于核 k-means 成本函数的 1+epsilon 逼近度。
Jun, 2017
通过基于随机化 K-means 算法的优化 Nystrom 方法,本文提出了一种能适用于大规模数据集的低秩近似计算算法,使得在高维数据集上能够以较小的准确性损失实现更高的计算效率。
Dec, 2016
这篇文章研究了用 Nyström 方法来进行核矩阵近似时的误差边界,着重介绍了基于积分算子浓度不等式和压缩感知理论的两种方法,通过改善误差边界,使得在大本征间隔下,使用 Nyström 方法进行核分类时可以显著减少支持向量的数量,并且不严重损害分类的性能。
Nov, 2011
本文研究文献中关于维数约减最常讨论的算法之一,即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人(2008)中算法的新颖分析方法,可以得出尖锐的估计和关于其性能的新见解。通过实验,我们证明了我们预测的紧密性与经验观测的一致性。
Aug, 2013