低秩约束下的大规模凸优化

ICMLJun, 2011

Large-Scale Convex Minimization with a Low-Rank Constraint

Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir

TL;DR针对在低秩矩阵中最小化凸函数的问题，本文提出了一种高效的贪心算法，并给出其形式化的逼近保证。算法的每次迭代都涉及到计算某个矩阵的最大奇异值对应的左、右奇异向量，这可以在线性时间内完成。该算法可应用于矩阵完成和鲁棒低秩矩阵逼近等多个领域中的大型矩阵问题。

Abstract

We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (

convex function low-rank matrices singular vectors matrix completion collaborative filtering

发现论文，激发创造

限制排名凸优化的局部搜索算法

本文提出了贪心算法和局部搜索算法用于秩约束凸优化，实现矩阵填充和鲁棒主成分分析，并且在理论上得到了优化，同时提出了更实用和高效的变体算法。

Jan, 2021

低秩矩阵优化的非凸几何

本文针对两个广泛使用的最小化问题：凸函数最小化问题和加上核范数的凸函数最小化问题，提出使用低秩分解和替代核范数的方法来加速求解问题，并证明其可以在全局范围内找到最优解。

Nov, 2016

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

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

Oct, 2008

结构化低秩矩阵学习：算法与应用

该论文提出了一种新的因子分解模型，它将低秩矩阵和线性子空间约束分离开来，从而使得优化问题在 Riemannian spectrahedron 流形上得以求解。实验证明，该方法在标准 / 鲁棒 / 非负矩阵补全，Hankel 矩阵学习和多任务学习等问题上具有较高的效率。

Apr, 2017

高效的结构化矩阵秩最小化

利用核范数正则化寻找结构化低秩矩阵的问题，我们采用线性映射来编码结构，并提出了一种更有效的方法，与同类方法相比，该方法在迭代次数和计算成本上都有所改善，并在随机系统实现和光谱压缩感知问题中表现出色。

Sep, 2015

结构化低秩矩阵分解：全局最优、算法和应用

本文研究了一种适用于大规模数据集且通过使用特定形式的正则化来捕获因素中的额外结构的矩阵分解技术，该技术将已知的正则化器（如总变化和核范数）作为特定情况。尽管所得到的优化问题是非凸的，但我们证明如果因素的大小足够大，在某些条件下，任何因素的局部最小值都可以得到全局最小值。我们还提供了一些实用的算法来解决矩阵分解问题，并导出了给定近似解的距离与全局最优解之间的距离范围。在大数据集上，神经钙成像视频分割和高光谱压缩恢复的示例显示了我们的方法的优势。

Aug, 2017

快速低秩矩阵学习与非凸正则化

本文提出了一种基于截断的异性低秩正则化方法，通过使用功率方法逼近奇异值分解以提高计算效率，相比于传统核范数正则化方法，实验结果表明所提出的方法在矩阵补全领域有更快的速度和更高的准确率。

Dec, 2015

奇异值投影保证秩最小化

本文提出了一个名为 SVP (Singular Value Projection) 的快速且有效的算法，用于解决在严格是 ometry 约束下的等式约束的秩最小化问题以及低秩矩阵补全问题，实验结果表明，该算法相较于现有算法表现更好，更鲁棒性更强。

Sep, 2009

低秩矩阵优化中的全局最优性

本文研究将矩阵分解后进行优化以减少计算量，并分析了具有全局收敛特性的目标函数

Feb, 2017

低秩外梯度方法用于可扩展半定规划优化

我们研究了涉及具有凸目标函数（平滑或非平滑）和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题，这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况，在这种情况下，问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果，证明在这些情况下，众所周知的 Extragradient 方法，在在接近最优原始 - 对偶解的位置初始化时，使用低秩奇异值分解（SVD）将收敛到约束优化问题的解，并具有标准收敛速度保证，而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。

Feb, 2024