Nov, 2014
有限样本下精确快速矩阵补全
Fast Exact Matrix Completion with Finite Samples
Prateek Jain, Praneeth Netrapalli
TL;DR该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O (nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。
Abstract
matrix completion is the problem of recovering a low rank matrix by observing
a small fraction of its entries. A series of recent works [KOM12,JNS13,HW14]
have proposed fast →
发现论文，激发创造
无需考虑条件数的快速矩阵填充
本文介绍了第一种算法，可在多项式时间和样本复杂度内完成矩阵补全，其复杂度与矩阵的秩成正比，与矩阵的维度成线性关系，与矩阵的条件数成对数关系，并基于交替最小化扩展算法，对标准假设下受噪声影响的情况也有理论保证。
Jul, 2014
来自一般确定性采样模式的矩阵补全
该论文针对低秩矩阵完成算法的理论保证存在严格且近似的情况，可以应用于任何确定性采样计划。通过引入一个图形来解决观察条目的性能问题，论文从理论和实验角度论证了算法的成功性。
Jun, 2023
受限强凸性与加权矩阵补全：带噪声的最优界限
该研究针对一种形式的行 / 列加权采样的矩阵完成问题进行了分析，提出了一种基于 $M$-estimator 的技术，通过对解的秩和 spikiness 同时进行控制，在加权 Frobenius 范数下建立了一些误差界限，其中关于矩阵的 “spikiness” 和 “low-rankness” 的度量比以前的工作限制更少。
Sep, 2010
通用矩阵补全
提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案，可以精确地恢复所有满足一定不相干性条件的低秩矩阵，而只需 O（nr^2）个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析，与之相比，其样本复杂度为 O（nrlogn）
Feb, 2014