本文提出了一种特定偏向分布的采样方式，利用该采样方式可以从少量采样的数据中精确恢复任何秩为r的nxn的矩阵（无需满足之前已有的结构限制要求），而且在没有先验信息下本文建立了三种使用该采样方式的方法，其中还包括分析了针对非均匀采样情形中，加权核范数/迹范数惩罚的优点。

Jun, 2013

提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案，可以精确地恢复所有满足一定不相干性条件的低秩矩阵，而只需O（nr^2）个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析，与之相比，其样本复杂度为O（nrlogn）

Feb, 2014

本文证明了矩阵完成问题即使假设未知矩阵的秩为4并且允许输出任意常数秩的矩阵，以及假设未知矩阵不相干并展示90%的条目，在4着色问题的推测难度性的基础上，矩阵完成问题仍然是计算上难解的；而在标准假设P≠NP下，对于正半定矩阵完成问题，我们也展示了类似的难度结果。

Feb, 2014

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

Jul, 2014

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

Nov, 2014

本文介绍了一种基于Leave-one-out方法的技巧用于解决低秩矩阵完成问题，进而通过对Projected Gradient Descent和nuclear norm minimization等算法进行分析，得到了这些算法的收敛性保证以及较为精细的界限。

Mar, 2018

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

May, 2023

该论文针对低秩矩阵完成算法的理论保证存在严格且近似的情况，可以应用于任何确定性采样计划。通过引入一个图形来解决观察条目的性能问题，论文从理论和实验角度论证了算法的成功性。

Jun, 2023

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

Feb, 2024

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

Jun, 2024