Nov, 2009

随机矩阵逼近方案的误差界

PDF
TL;DR本文研究了在多种范数下，通过稀疏随机矩阵 X 逼近实数矩阵 A 的问题，其中包括了图算法中更适用的 $(\infty,1)$ 范数和 $(\infty,2)$ 范数。文章提出的界限适用于大多数随机稀疏化模式，证明了 $(\infty,1)$ 和 $(\infty,2)$ 误差评估的最优性。文章还给出了当 X 的元素被均匀限制时三个范数的浓度结果。
randomized matrix sparsificationgraph algorithmsapproximation errorspectral norm$(\infty,1)$ norm
发现论文，激发创造
  • 具有独立条目的随机矩阵范数的尖锐非渐进界限

    本文研究了具有独立条目的随机矩阵的谱范数的非渐进界，并在子高斯分布和矩阵形状方面进行了扩展，该方法基于矩法和几何泛函分析技术。本文还研究了具有 Rademacher 分布的矩阵的规范并证明了谱边缘的相位转变行为。

    Aug, 2014

  • 通过随机张量谱范数的界限进行张量稀疏化

    该研究提出了一种元素稀疏化算法，基于张量的幂次进行，以及使用了一个用于较好的随机张量估计的不等式，旨在解决张量稀疏化问题并获得新的精度界限以改善算法性能。

    May, 2010

  • 大矩阵取样：一种基于几何函数分析的方法

    通过研究矩阵的随机子矩阵，证明了用最小可能 O（rlogr）的随机子矩阵（其中 r 是矩阵的数值秩），可以近似计算其谱范数，并给出了在该领域中的最优保证，并使用概率论的方法。Banach 空间中的操作型随机变量的大数定律证明了其工作原理。

    Mar, 2005

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

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

    Apr, 2017

  • 朴素 Nystrom 扩展的谱范数误差

    本文提供了第一个对于使用 Nystrom extension 过程中的谱范数误差的相对误差边界，该边界基于该问题与列子集选择问题的自然联系，最主要的工具为不重复抽样的矩阵切诺夫边界。

    Oct, 2011

  • 独立随机矩阵之和的预期范数：基础方法

    本文为一个基于随机矩阵的泛函分析不等式提供了完整、简明的证明。

    Jun, 2015

  • 随机内积核矩阵的谱范数

    本文研究了一种内积核随机矩阵模型，证明其经验谱分布在大 $n$ 和 $p$ 极限下收敛于一定的测度。通过将其与一个具有相同极限谱的 GUE 矩阵的轨迹矩进行比较，研究了奇数内核函数的情况，该矩阵的谱范数几乎必定收敛于极限谱的边缘。本研究的动机是分析一种利用协方差阈值处理来统计检测和估计稀疏主成分的方法，并且本文的结果表征了样本协方差矩阵在零设置下的最大特征值极限。

    Jul, 2015

  • 谱逼近的矩、随机游走和极限

    研究通过给出（有噪声的）矩的测量值来近似一维分布的问题的下限。

    Jul, 2023

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

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

    May, 2010

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

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

    Jul, 2015