Apr, 2023

Krylov 方法在低秩近似中（几乎）是最优的

PDF
TL;DR本文通过矩阵向量乘积模型和多种 Schatten norm 下的 rank-1 低秩逼近问题，证明了 Krylov methods 几乎达到了谱（p=∞）、Frobenius（p=2）和核（p=1）LRA 的信息论最优矩阵向量乘积数量的上界，并给出了一些改进的上界。
low-rank approximationschatten normskrylov methodsmatrix-vector product modelupper bounds
发现论文，激发创造
  • 入项变换矩阵乘积的低秩逼近难度

    在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。

    Nov, 2023

  • 低秩矩阵值 Chernoff 界和近似矩阵乘法

    本文提出了一种利用两种不同抽样方法进行矩阵乘法，以逼近具有谱范数的矩阵，从而得出理论上的界限。

    May, 2010

  • 稳定秩下的最优近似矩阵乘积

    用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

    Jul, 2015

  • 矩阵近似乘法及其在线性嵌入方面的应用

    该论文研究了计算两个实矩阵乘积的近似算法，提出了核秩的概念，并应用于线性低维嵌入中，使得任何核秩有界的欧几里得点集能够在独立于输入维度的投影空间上实现加性误差保证。

    Mar, 2014

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

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

    Sep, 2020

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

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

    Apr, 2017

  • Kronecker 乘积回归和低秩逼近的最优素描

    本研究旨在提出一种高效的 Kronecker 乘积回归算法，该算法可以用于矩阵逼近和低秩逼近，并且小于 2 的 p 值具有更好的运行时间，此外，还提出了一种用于所有成对差异的回归问题的算法。

    Sep, 2019

  • 从一阶测量中恢复低秩矩阵

    本文研究了通过核范数最小化从采样测量中恢复 Hermite 低秩矩阵的问题，其中测量是 Frobenius 内积形式的随机秩一矩阵，我们导出了确保成功恢复矩阵所需的测量数的界限，同时证明了测量扰动的鲁棒性和近似 4 - 设计对相位恢复的一般性限制。

    Oct, 2014

  • 当大数据实际上是低秩的，或者是某个函数生成的矩阵的逐个近似

    通过对两个 m 维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于 m 具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中 n×n 由函数生成的矩阵可以在与维度 m 无关的情况下以 O (log (n)ε^(-2) polylog (ε^(-1))) 的逐个元素误差逼近。我们还将我们的论点扩展到了由 m 维变量的多线性积生成的张量的低秩张量列逼近。我们在 Transformer 神经网络的注意力低秩逼近的背景下讨论了我们的结果。

    Jul, 2024

  • 通过采样杠杆元素实现更紧凑的低秩近似

    本文提出了一种新的随机算法，该算法采用特别偏向采样的方法，使误差最小化，可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近，并具有 better dependence on error ε，是一种高度可并行化的优化方法。此外，本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。

    Oct, 2014