最优低秩矩阵完成：半定松弛和特征向量分离

May, 2023

最优低秩矩阵完成：半定松弛和特征向量分离

Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

Dimitris Bertsimas, Ryan Cory-Wright, Sean Lo, Jean Pauphilet

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

Abstract

low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible, and has numerous applications such as product recommendation. Unfortunately, existing methods for solving →

low-rank matrix completion optimality-oriented convex relaxations disjunctive branch-and-bound certifiable optimality

发现论文，激发创造

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

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

Mar, 2009

噪声矩阵填充：通过非凸优化理解对凸松弛的统计保证

本文研究了针对大规模低秩矩阵的部分和带噪声数据中的矩阵补全问题，采用凸松弛和 Burer-Monteiro 方法，成功地将凸松弛的实践与非凸方法的统计保证相结合，取得了近乎最优的估计误差。

Feb, 2019

图上矩阵补全

本文提出了一种基于社区检测和流形学习的矩阵完成模型，通过约束矩阵在图上的平滑性来隐含地强制行和列之间的相似性，得到了比标准模型更好的矩阵恢复效果。

Aug, 2014

低秩矩阵补全的几何方法

针对低秩矩阵完成问题，本文提出了一种基于几何目标函数的优化算法，解决了 Frobenius 度量方法的无法连续和解集不闭合的困难，并为特殊完成方案提供了强大的性能保证。

Jun, 2010

基于凸化的离散感知矩阵补全的 l₀- 范数逼近

在结构化环境下，本文提出了一种改进的低秩矩阵补全方法，通过引入离散字母表集合，使用基于连续可微函数的分数规划方法规范离散性，从而比现有方法和基于 L1 范数的离散感知矩阵补全方法具有更好的性能。

May, 2024

矩阵补全的奇异值阈值算法

本文介绍了一种新的算法，用于近似矩阵和满足一组凸约束条件的所有矩阵中具有最小核范数的矩阵。该算法可在低阶矩阵完成问题上使用，具有快速计算的特点，通过少量存储空间实现低计算代价。

Oct, 2008

矩阵填充无虚假局部极小值

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

May, 2016

低秩矩阵完成的确定性理论

使用图极限理论规定的某一必要且充分条件，对于一系列矩阵补全问题，只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解，该理论是完全确定性的，没有随机性假设，同时列出了一些未解决的问题。

Oct, 2019

刚体理论下的低秩矩阵完备性唯一性

矩阵完成问题和距离几何问题之间具有类似性质，利用刚性理论的工具，可以设计出用于测试矩阵局部或全局唯一完成性的高效随机算法。

Feb, 2009

非相干最优矩阵完成

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

Oct, 2013