可证明地补全任意低秩矩阵

Jun, 2013

Completing Any Low-rank Matrix, Provably

Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, Rachel Ward

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

Abstract

matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constrain

matrix completion low-rank matrix sampling leverage scores weighted nuclear norm

发现论文，激发创造

从任何基础中的少量系数中恢复低秩矩阵

本文提出了新技术，用于分析低秩矩阵恢复的问题，利用基展开系数，在给定的矩阵基的任何情况下，从仅随机采样的展开系数中有效地重构秩为 r 的未知 n x n 矩阵。同时，我们探讨了对于所有低秩矩阵同时具有不相干性的运算符基，所需随机采样的展开系数数目并进行了细致的讨论。

Oct, 2009

关于矩阵完成和逼近中自适应能力的探讨

本文介绍了一种自适应采样算法，可以高效地完成低秩近似和矩阵填充任务，并且消除了之前文献中存在的某些限制性假设，具有更好的采样复杂度。

Jul, 2014

通用矩阵补全

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

Feb, 2014

矩阵补全的计算限制

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

Feb, 2014

凸优化法实现精确矩阵补全

通过解决凸优化问题，可以从数据矩阵的不完全采样中完美地恢复低秩矩阵，并且这个结果被扩展到了压缩感知。

May, 2008

自适应采样的低秩矩阵和张量补全

研究低秩矩阵和张量完成，提出了采用自适应抽样方案的新算法，它们具有强大的性能保证，并能够恢复具有噪声干扰的低秩矩阵。

Apr, 2013

凸松弛的威力：近似最优矩阵补全

该论文探讨了如何从其少量项目中恢复未知矩阵的问题，提出使用 “核规范” 法将矩阵恢复降低至在信息论极限附近的数列，以有效提高了恢复矩阵的准确性。

Mar, 2009

来自一般确定性采样模式的矩阵补全

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

Jun, 2023

在矩阵中识别有影响力的条目

提出一个针对矩阵完成问题的概率分布，它能够显示矩阵中最具影响力的项；从理论和实验两个角度证明了这种方法的有效性和实用性。

Oct, 2013

非相干最优矩阵完成

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

Oct, 2013