通过新的分析方法，本文提出了统一的不等式并改进了以往矩阵恢复方法的采样复杂度，同时探讨了低秩加稀疏矩阵分解问题的可解性。

Oct, 2013

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

Jul, 2014

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

Nov, 2014

该研究提出了一种可证明，高效的在线算法，用于矩阵完成问题。该算法使用随机梯度下降，具有快速的更新时间，并可自然地用于离线设置。

May, 2016

本文介绍了如何通过改进梯度下降的技术和方法，将矩阵填充的采样率由O(poly(条件数)*mu^3*r^3*log^3n/n)降低至O(mu^2*r^2*条件数^14*log(n)/n)，并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。

Jan, 2019

提出了一个迭代算法，用于低秩矩阵完成，可以解释为迭代重新加权最小二乘（IRLS）算法和应用于非凸秩代理目标的鞍点逃逸平滑牛顿方法，它结合了先前IRLS方法的有利数据效率与几个数量级的可伸缩性的改进。我们的方法在样本数量接近信息理论极限时就达到了局部二次收敛速度，并在数值实验中表明，与许多现有方法不同，我们的方法能够在样本很少的情况下完成条件数高达$10^{10}$的非常病态的矩阵。

Sep, 2020

本文研究了在低噪声环境下使用iid子高斯噪声的归纳矩阵填充问题（带侧面信息的矩阵填充），首次获得了普适性界限，并呈现出标准差与零误差恢复情况下的规模趋近，结果表明：在样本大小趋近于无穷大时，噪声即使存在也会趋近于零，对于侧面信息的固定维度而言，它们只有对矩阵大小的对数依赖性。

Dec, 2022

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

May, 2023

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

Feb, 2024

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

Jun, 2024