Aug, 2017

通过 QR 分解改进的固定秩 Nyström 逼近：实践和理论方面

PDF
TL;DR本文探讨标准 Nystrom 方法在排名降低方面存在的缺点，提出了一种修改方法以改进 Nystrom 逼近的固定排名。通过理论分析和数值实验来证明修改方法优于标准 Nystrom 方法，在很多情况下具有极高的精度，是最优的，并与标准 Nystrom 方法具有几乎相同的计算复杂度。
nystrom methodkernel matricesrank reductionnumerical experimentscomputational complexity
发现论文，激发创造
  • 大规模核机器的随机聚类 Nystrom

    通过基于随机化 K-means 算法的优化 Nystrom 方法，本文提出了一种能适用于大规模数据集的低秩近似计算算法，使得在高维数据集上能够以较小的准确性损失实现更高的计算效率。

    Dec, 2016

  • 提高 Nyström 方法在低秩近似中的精度

    本文提出了一系列启发式策略，使 Nyström 方法在 nonsymmetric 或 rectangular 矩阵中具有高准确度，通过交替方向细化过程，将 Nyström 方法和瘦秩揭示分解作为快速枢轴策略。

    Jul, 2023

  • 矩阵低秩逼近的文献综述

    本文介绍了低秩逼近技术，并给出了众多相关技术的广泛参考资料。在此基础上，简要评述了基于奇异值分解、QR 分解、随机算法以及交叉 / 骨架逼近等各种低秩逼近技术的应用和优缺点。

    Jun, 2016

  • Nyström 方法的递归抽样

    本文首次提出一种核 Nystr"om 逼近算法，它在所有核矩阵中都具有可证明的准确性，且其运行时间与训练点数成线性关系，并利用快速递归采样方案，实现了基于支撑点的快速采样，相较于常用技术如均匀采样 Nystr"om 逼近和随机 Fourier 特征方法，找到更精确、低秩的核逼近方法的速度更快。

    May, 2016

  • 快速稳定的随机低秩矩阵逼近

    该论文对一种适用于一般矩阵的 Nystr {"o} m 方法进行了研究，并表明它的近似质量接近其他竞争方法，在数值稳定性方面表现良好。文中阐述了该方法的计算成本，并演示了可以在更新和降低矩阵时使用该方法。

    Sep, 2020

  • 利用随机性发现结构：构造近似矩阵分解的概率算法

    本文介绍了一种用于构建随机算法的模块化框架，以进行矩阵分解，通过随机抽样识别矩阵的大部分内容，并将输入矩阵压缩到子空间，这种方法在精度、速度和鲁棒性方面都比传统方法更具优势，能够更好地解决大数据集合的问题。

    Sep, 2009

  • 低秩矩阵分解的随机算法：尖锐性能界限

    本文研究文献中关于维数约减最常讨论的算法之一，即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人（2008）中算法的新颖分析方法，可以得出尖锐的估计和关于其性能的新见解。通过实验，我们证明了我们预测的紧密性与经验观测的一致性。

    Aug, 2013

  • Nystrom 方法的改进界限及其在核分类中的应用

    这篇文章研究了用 Nyström 方法来进行核矩阵近似时的误差边界，着重介绍了基于积分算子浓度不等式和压缩感知理论的两种方法，通过改善误差边界，使得在大本征间隔下，使用 Nyström 方法进行核分类时可以显著减少支持向量的数量，并且不严重损害分类的性能。

    Nov, 2011

  • 基于流数据的半正定矩阵固定秩近似

    本文提出了一种新的算法，利用 Nystrom 逼近和截断秩的新机制实现了从草图中进行固定秩正半定逼近，并证明了在 Schatten 1 - 范数中可以实现任何预设的相对误差，能够利用输入矩阵的谱衰减，并在计算机实验中表现出比固定秩正半定矩阵逼近的替代技术更好的性能。

    Jun, 2017

  • 带 Nystrom 近似的可扩展核 K-means 聚类：相对误差界限

    通过将线性 k - 均值聚类应用于使用称为等级限制的 Nyström 近似构造的 {k/epsilon}(1+o (1)) 特征，本文分析了该范例应用于核 k - 均值聚类，并表明相对于不使用 Nyström 方法提供的保证，计算出的群集分配会满足相对于核 k-means 成本函数的 1+epsilon 逼近度。

    Jun, 2017