May, 2013

Nystroöm 方法在矩阵压缩中的应用

PDF
TL;DR介绍了如何使用 Nyström 方法来寻找一般矩阵的奇异值分解和方阵的特征值分解，从而得到压缩版本的矩阵，并在选择 A_M 方面提出了一个好的初始采样算法，适用于一般矩阵和核矩阵。
nyström methodsingular value decompositioneigenvalue decompositionapproximate computationpivoted version
发现论文，激发创造
  • 快速稳定的随机低秩矩阵逼近

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

    Sep, 2020

  • 随机奇异值分解的一般化

    本文介绍了随机 SVD 方法的推广版，使用多元高斯向量代替标准高斯向量进行矩阵 - 向量乘积，以允许将先前的知识加入算法中，进而探索基于高斯过程函数的 Hilbert-Schmidt（HS）算子的随机 SVD 的连续模拟。文中提出了一种新的基于加权 Jacobi 多项式的协方差核，从而使随机生成的函数具有良好的平滑性，再通过数值实验证明其适用性。

    May, 2021

  • 从压缩测量中恢复谱特征的描绘 SVD

    本文考虑一种流式数据模型，通过计算奇异值分解和草图矩阵，获得与原始数据矩阵非常接近的奇异值和奇异向量。同时，将其应用于流图算法来近似计算具有低秩的计算机网络图 Laplacian 的特征值和特征向量。

    Nov, 2012

  • 压缩谱嵌入：避开 SVD

    本文提出一种基于随机投影与有限阶多项式拓展计算奇异值分解嵌入的压缩光谱嵌入算法，其降维效果与计算复杂度不受特征向量数量影响。此算法对聚类和分类等下游推断任务的对比相似度度量具有较好效果。

    Sep, 2015

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

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

    Jul, 2023

  • 基于 t - 积的随机张量奇异值分解

    本文介绍了一种利用随机矩阵方法扩展张量 SVD 来压缩和分析数据集的方法，相对于 t-SVD，具有更高的计算效率，并提供了该算法的详细说明和数值结果。

    Sep, 2016

  • 使用 t-SVD 进行精确张量补全

    本文利用张量奇异值分解求得张量的秩概念 —— 张量管秩，使用具有优化性质的张量核范数最小化的凸优化问题，完成了从有限采样中完成高维数据恢复的任务，并证明了此方法的有效性。

    Feb, 2015

  • 健壮的 SVD 简化版：大规模数据分析的快速可靠算法

    本研究提出了一种高效的算法，叫做球形归一化奇异值分解 (SVD)，用于稳健的奇异值分解近似，对异常值不敏感、可扩展的计算，提供准确的奇异向量估计。该算法通过仅使用标准降秩奇异值分解算法对适当缩放的数据进行两次计算，实现了显著的计算速度，并在计算时间上明显优于竞争算法。为评估估计奇异向量及其子空间的稳健性，我们引入了矩阵型输入的新的破坏点概念，包括按行、按列和按块的破坏点。理论和实证分析表明，与标准 SVD 及其修改相比，我们的算法具有更高的破坏点。我们在高维微阵列数据集的鲁棒低秩逼近和鲁棒主成分分析等应用中，经验地验证了我们方法的有效性。总体而言，本研究提供了一种高效且稳健的 SVD 近似解决方案，克服了现有算法在异常值存在时的局限性。

    Feb, 2024

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

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

    Nov, 2011

  • 超越快速矩阵乘法的频谱逼近：算法与难度

    本文提出一项新的算法，使用随机痕量估计方法，多项式逼近，以及快速系统求解器等高效地获得一个矩阵的奇异值谱的直方图，并用其来求解一类对称矩阵范数。同时，证明了精度高的算法可以在次立方时间内进行矩阵乘法，从而限制了计算有效电阻的难度。

    Apr, 2017