Matrix Completion with Convex Optimization and Column Subset Selection

我们提出了一种矩阵恢复问题的两步方法。我们的方法结合了列子集选择和低秩矩阵完成问题的理论基础。所提出的方法在每个步骤中都解决了一个凸优化问题。我们提出了两种算法来实现我们的列选择矩阵完成（CSMC）方法，每种算法专门用于不同大小的问题。我们对所提出的方法进行了正式分析，其中我们制定了必要的假设和找到正确解的概率。在论文的第二部分中，我们展示了实验工作的结果。数值实验验证了算法的正确性和性能。为了研究矩阵大小、秩和缺失元素比例对解的质量和计算时间的影响，我们在合成数据上进行了实验。所提出的方法应用于两个实际问题：推荐系统中电影评分的预测和图像修复。我们的彻底分析表明，CSMC提供了与基于凸优化的矩阵完成算法相当的解决方案质量。然而，CSMC在运行时间方面具有显着的节省。

矩阵恢复问题，即如何从部分观测到的矩阵中恢复出完整的矩阵。

该论文提出了一种两步法的矩阵恢复方法，结合了列子集选择和低秩矩阵完成问题的理论基础，并在每一步中解决一个凸优化问题。

该方法在合成数据和两个实际问题（电影推荐和图像修复）上的实验结果表明，它提供了与基于凸优化的矩阵完成算法相当的质量解，但在运行时间上具有显着的节省。

最近的相关研究包括基于凸优化的矩阵完成方法和其他矩阵恢复方法，如低秩矩阵分解和矩阵近似。