证明对于任意实值矩阵 X，在正整数 r≥k 的情况下，存在 X 的 r 个列的子集，将 X 投影到其中一个列的线性组合中，得出的结果将是 Frobenius 范数下的 X 的最佳秩 - k 逼近的一个近似值等于 sqrt ((r + 1)/(r-k +1))。并提出一个确定性算法可在 O (r n m^ω log m) 时间内找到这样的列的子集，其中 ω 是矩阵乘法的指数。同样，我们提供了一种更快的随机算法，可在 O (r n m^2) 时间内进行运算。

Apr, 2011

本文研究了在正定核框架下的监督学习问题，提出了基于随机矩阵列采样的核矩阵低秩近似方法，此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题，同时保持预测性能不变。

Aug, 2012

我们提供了一个解决低秩矩阵完成问题的新框架，通过聚合涉及观测的回归问题的解来将矩阵 M 完成，并改进了之前已知的算法的样本复杂度和运行时间。

Aug, 2023

本文介绍了第一种算法，可在多项式时间和样本复杂度内完成矩阵补全，其复杂度与矩阵的秩成正比，与矩阵的维度成线性关系，与矩阵的条件数成对数关系，并基于交替最小化扩展算法，对标准假设下受噪声影响的情况也有理论保证。

Jul, 2014

本文主要研究矩阵乘法相关问题，提出了一种新算法，相比于之前的算法能够更快地计算带有权值的有向图中的所有点对最短路径问题和稀疏矩阵的乘法问题。

Apr, 2012

本文介绍了一种计算部分秩相因分解的方法，该方法采用随机取样避免了列交换，从而使得计算速度得到了大幅提升，并且在各种矩阵上都表现出色，特别是在 GPU 结构上表现尤为突出。

Mar, 2015

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

Sep, 2020

本文探讨矩阵的秩约束 Frobenius 范数逼近问题，即对于 $m$ 乘 $n$ 矩阵 $A$，求出秩不超过 $k$ 的矩阵。

Mar, 2006

该论文提出了一种在矩阵具有低相干性的情况下，基于差分隐私的低秩逼近算法，在准确性、效率方面优于随机响应算法。

Nov, 2011

研究表明，许多快速递归矩阵乘法算法在范数意义下是稳定的，基本所有标准线性代数运算，包括 LU 分解、QR 分解、线性方程求解、矩阵求逆、最小二乘问题求解、特征值问题和奇异值分解等均可在 O（n^（ω+η））的时间复杂度内稳定地完成。

Dec, 2006