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

Jul, 2014

该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O(nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。

Nov, 2014

矩阵分解是一种常用的大规模矩阵补全方法，本文提出了一种理论保证，即在正则化条件下，优化算法可以收敛于矩阵分解的全局最优解，并恢复真实的低秩矩阵，其中的非对称矩阵分解的扰动分析是一项技术贡献。

Nov, 2014

本文探讨了解决基本的机器学习问题——矩阵补全的方法，并证明了普遍使用的非凸优化问题在正半定矩阵补全中没有局部极小值，可用于任意初始化的优化算法，并可在多项式时间内证明其正确性。

May, 2016

本文提出了一种简单的投影梯度下降方法来估计低秩矩阵，用于解决鲁棒矩阵完成问题，并且包括清除一些受损条目的步骤，并在低秩矩阵完成问题中获得了最优观测次数和最优破坏次数的解决方法。同时，本文的结果还意味着，对于低秩矩阵完成问题的时间复杂度界限，取得了重要的改进。最后，通过将结果应用于鲁棒PCA问题，得到了高效的解决方案

Jun, 2016

发展了一种新框架，旨在捕捉一般非凸低秩矩阵问题的共同局面，包括矩阵感知，矩阵完成和鲁棒PCA，在优化风景线的现有分析的基础上进行了连接和简化，自然地导致了不对称矩阵完成和鲁棒PCA的新结果

Apr, 2017

通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题，并实施一个可证明最优的分离分支限界方案，推导出一类新的收敛松弛方法。数值实验表明，相比现有的收敛松弛方法，我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外，我们展示了我们的分离分支限界方案的性能，并展示了它在解决矩阵完成问题方面的优异表现。

May, 2023

对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。

Feb, 2024

低秩矩阵补全问题关注使用稀疏观测的一组观测条目来估计矩阵中未观测的条目。我们考虑非均匀设置，其中观测条目根据高度变化的概率进行采样，可能具有不同的渐近尺度。我们证明了在结构化采样概率下，使用较小的子矩阵而不是整个矩阵上运行估计算法通常更好，有时是最优的。特别地，在某些条件下，我们证明了适用于每个条目的错误上界，这些错误上界与最小化下界相匹配。我们提供了数值实验证实了我们的理论发现。

Feb, 2024

对称半正定低秩矩阵完成问题进行研究，包括确定性依赖于矩阵元素的采样。首先通过实验证明该问题的全局最优点与梯度下降算法具有难以收敛的关系，但证明了在矩阵因子的秩较小且满足一定假设的情况下，非凸目标函数在一个低秩矩阵附近的商流形上是测地强凸的。此外，通过实验证明所提出的GD初始参数设计能够保证收敛到全局最小值。还进行广泛实验，比较了不同初始化、噪声水平、维度和秩对MC方法的收敛性和完成性能的影响。

Jun, 2024