Mar, 2024

凸优化与列子集选择的矩阵补全

PDF
TL;DR我们介绍了一种用于矩阵恢复问题的两步方法，结合了列子集选择和低秩矩阵补全问题的理论基础。该方法通过两个凸优化任务来求解，我们提出了两个算法来实现 Columns Selected Matrix Completion（CSMC）方法，分别针对不同规模的问题。我们对该方法进行了正式的分析，在分析中我们给出了必要的假设和找到正确解的概率。在论文的第二部分，我们展示了实验结果。通过在合成数据上进行实验，我们研究了矩阵大小、秩和缺失元素比例对解的质量和计算时间的影响。该方法还应用于两个实际问题：推荐系统中的电影评分预测和图像修复。我们的彻底分析显示 CSMC 能够提供与基于凸优化的矩阵补全算法相当的解的质量，但在运行时间上具有显著的节省。
发现论文，激发创造
  • 图上矩阵补全

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

    Aug, 2014

  • 近乎最优的鲁棒矩阵完成

    本文提出了一种简单的投影梯度下降方法来估计低秩矩阵，用于解决鲁棒矩阵完成问题，并且包括清除一些受损条目的步骤，并在低秩矩阵完成问题中获得了最优观测次数和最优破坏次数的解决方法。同时，本文的结果还意味着，对于低秩矩阵完成问题的时间复杂度界限，取得了重要的改进。最后，通过将结果应用于鲁棒 PCA 问题，得到了高效的解决方案

    Jun, 2016

  • 剪裁矩阵补全：解决天花板效应

    本研究提出了一种 trace-norm 最小化算法及正则化项，以提高对修剪矩阵完成（CMC）的精确恢复率，并在推荐系统方面通过综合评估所提出的方法的有效性。

    Sep, 2018

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

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

    May, 2008

  • 带噪声的矩阵完成

    本研究论文介绍新兴的矩阵填充技术及其应用，其中最简单的情况是从一个数据样本中恢复一个数据矩阵。本文提出通过核范数极小化技术，按数据约束条件恢复矩阵，可在一定程度下证明矩阵填充的准确性，数值结果表明，核范数极小化技术可以在很少的观测样本中准确填充低秩矩阵的许多缺失条目。

    Mar, 2009

  • 基于列操作的矩阵补全：近似最优的样本鲁棒性与秩之间的平衡

    本文解决了一种矩阵完成问题，特别是当某些列完全且任意被污染，通过一个修剪和凸程序的组合，最小化核范数和 l (1,2) 范数，我们的理论结果表明，即使观察到的条目比例很小，也可以完成底层矩阵，即使被污染的列的数量增加，还可以进行矩阵完成。

    Feb, 2011

  • 高阶矩阵完成和子空间聚类与缺失数据

    该文章研究了一个矩阵完成问题，该问题假设矩阵的列属于多个低秩子空间的并集，这将标准的低秩矩阵完成问题推广到了矩阵秩可以相当高或甚至是完全秩的情况。文章的主要结果表明，每一列可以从不完整的版本中完美地恢复出来，只要在均匀随机地观察至少 CrNlog^2 (n) 个条目的情况下，其中 C>1 是依赖于非相干条件、子空间的几何排列和列在子空间中的分布的常数，结果通过数字实验和应用于互联网距离矩阵完成和拓扑识别来加以说明。

    Dec, 2011

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

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

    Mar, 2009

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

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

    May, 2023

  • 低秩矩阵补全的几何方法

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

    Jun, 2010