证明对于任意实值矩阵 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

提出一种行列仿射测量方案以及相应的算法，可用于低秩矩阵恢复，具有较高的精度。

May, 2015

提出了一种基于随机列抽样的多项式时间算法，用于选择具有良好谱特性的矩阵子集，具有较高的计算效率和实用价值，并结合 Grothendieck 因子分解构造了一种新的近似算法，以计算矩阵的（无穷大，1）范数。

Jun, 2008

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

Sep, 2020

利用核范数正则化寻找结构化低秩矩阵的问题，我们采用线性映射来编码结构，并提出了一种更有效的方法，与同类方法相比，该方法在迭代次数和计算成本上都有所改善，并在随机系统实现和光谱压缩感知问题中表现出色。

Sep, 2015

本文通过最小化矩阵的核范数，结合已知信息来重建未知的低秩矩阵，并证明了在满足特定的 “不连贯条件” 的情况下，所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作，相较于之前的结果，提供了更好的界限。

Oct, 2009

本文研究了一种矩阵的子集选择问题，其中关注了 Frobenius 范数和谱矩阵范数，并提出了多种新的逼近算法，并证明了在常数因子范围内逼近度是最优的，并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种影响。

Dec, 2011

本文提出了一种贪心算法来解决高秩矩阵子空间中低秩矩阵的基问题，并比较了其与其他方法的优劣，进而可应用于数据压缩，计算近多重特征值的精确特征向量，图像分离和图马拉锡算子的特征值问题。

Mar, 2015

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

Mar, 2005

本文提出了固定点迭代算法和 Bregman 迭代算法来解决核范数最小化的问题，并证明了前者的收敛性。通过使用同伦方法和近似奇异值分解过程，我们得到了一个非常快速，鲁棒和强大的算法，称为 FPCA（具有近似 SVD 的固定点连续化），它可以解决非常大的矩阵秩最小化问题。在随机生成和真实矩阵完成问题方面的数值结果表明，这个算法比如 SDPT3 等半定规划求解器更快，且能提供更好的恢复性能。在在线推荐，DNA 微阵列数据集和图像修复问题上的数值实验证明了我们算法的有效性。

May, 2009