快速稳定的随机低秩矩阵逼近
介绍了如何使用 Nyström 方法来寻找一般矩阵的奇异值分解和方阵的特征值分解,从而得到压缩版本的矩阵,并在选择 A_M 方面提出了一个好的初始采样算法,适用于一般矩阵和核矩阵。
May, 2013
本文研究文献中关于维数约减最常讨论的算法之一,即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人(2008)中算法的新颖分析方法,可以得出尖锐的估计和关于其性能的新见解。通过实验,我们证明了我们预测的紧密性与经验观测的一致性。
Aug, 2013
本文提出了一系列启发式策略,使 Nyström 方法在 nonsymmetric 或 rectangular 矩阵中具有高准确度,通过交替方向细化过程,将 Nyström 方法和瘦秩揭示分解作为快速枢轴策略。
Jul, 2023
本文介绍了低秩逼近技术,并给出了众多相关技术的广泛参考资料。在此基础上,简要评述了基于奇异值分解、QR 分解、随机算法以及交叉 / 骨架逼近等各种低秩逼近技术的应用和优缺点。
Jun, 2016
本文介绍了随机 SVD 方法的推广版,使用多元高斯向量代替标准高斯向量进行矩阵 - 向量乘积,以允许将先前的知识加入算法中,进而探索基于高斯过程函数的 Hilbert-Schmidt(HS)算子的随机 SVD 的连续模拟。文中提出了一种新的基于加权 Jacobi 多项式的协方差核,从而使随机生成的函数具有良好的平滑性,再通过数值实验证明其适用性。
May, 2021
本文提出一项新的算法,使用随机痕量估计方法,多项式逼近,以及快速系统求解器等高效地获得一个矩阵的奇异值谱的直方图,并用其来求解一类对称矩阵范数。同时,证明了精度高的算法可以在次立方时间内进行矩阵乘法,从而限制了计算有效电阻的难度。
Apr, 2017
本研究提出了一种高效的算法,叫做球形归一化奇异值分解 (SVD),用于稳健的奇异值分解近似,对异常值不敏感、可扩展的计算,提供准确的奇异向量估计。该算法通过仅使用标准降秩奇异值分解算法对适当缩放的数据进行两次计算,实现了显著的计算速度,并在计算时间上明显优于竞争算法。为评估估计奇异向量及其子空间的稳健性,我们引入了矩阵型输入的新的破坏点概念,包括按行、按列和按块的破坏点。理论和实证分析表明,与标准 SVD 及其修改相比,我们的算法具有更高的破坏点。我们在高维微阵列数据集的鲁棒低秩逼近和鲁棒主成分分析等应用中,经验地验证了我们方法的有效性。总体而言,本研究提供了一种高效且稳健的 SVD 近似解决方案,克服了现有算法在异常值存在时的局限性。
Feb, 2024
本文介绍一种 “softImpute” 算法,将 matrix-completion 问题的两种流行的方法:核范数规则化矩阵逼近和最大间隔矩阵分解结合,且在大矩阵逼近和补全方面表现更好。
Oct, 2014