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

ICLRJan, 2021

Local Search Algorithms for Rank-Constrained Convex Optimization

Kyriakos Axiotis, Maxim Sviridenko

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

Abstract

We propose greedy and local search algorithms for rank-constrained convex optimization, namely solving $\underset{\mathrm{rank}(A)\leq r^*}{\min}\, R(A)$ given a convex function $R:\mathbb{R}^{m\times n}\rightarrow \mathbb{R}$ and a parameter $r^*$. These algorithms consist of repeating two steps: (a) adding a new rank-1 matrix to $A$ and (b) enforcing the r

rank-constrained convex optimization greedy algorithm local search algorithm matrix completion robust principal component analysis

发现论文，激发创造

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

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

Jun, 2011

关于贪心低秩优化的近似保证

本文提供了一种新的矩阵估算近似保证方法，其基于约束强凸性和平滑性的标准假设。同时，本文揭示了低秩估算和组合优化之间的新联系，并针对两个重要的现实问题提供了贪心估计与基准估计间的经验比较。

Mar, 2017

Riemannian 优化在低秩矩阵补全中的保证

研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性，其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小，这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。

Mar, 2016

低秩矩阵恢复的黎曼优化保证

本文研究了低秩矩阵恢复的一类黎曼优化算法，证明了当感知算子的受限等距常数小于 Cκ/√r 时，算法能够从几乎最小的测量中恢复低秩矩阵。

Nov, 2015

严格低秩约束优化 -- 一种渐进 $O (rac {1}{t^2})$ 方法

我们研究了一类具有秩规范化的非凸非光滑问题，以促进最优解的稀疏性。我们提出了应用近端梯度下降方法来解决该问题，并通过一种新型的支持集投影操作加速过程，作用于中间更新的奇异值。我们展示了我们的算法能够达到收敛速度为 $O (rac {1}{t^2})$，这与 Nesterov 有关于光滑凸问题的一阶方法的最优收敛速度完全相同。可以期望严格的稀疏性，且在每次更新中奇异值的支持集是单调收缩的，这在基于动量的算法中是新颖的。

Jul, 2023

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

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

Feb, 2017

低秩矩阵优化的非凸几何

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

Nov, 2016

低秩二进制矩阵逼近问题的逼近方案

我们为一种关于二进制向量聚类的约束性问题提供了一种随机线性时间逼近方案，并且通过解决这个问题，我们获得了在二进制向量聚类和二进制矩阵低秩逼近方面的第一个线性时间逼近方案。

Jul, 2018

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

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

Mar, 2009

一种收敛的梯度下降算法，用于基于随机线性测量的秩降和半定规划

本研究提出了一种基于梯度下降的简单、可扩展、快速的算法来优化处理秩最小化问题及其相关的半定规划问题。通过对一个秩为 r 和条件数为 κ 的正半定 n x n 矩阵进行 O (r³κ²n log n) 次随机测量，我们证明了该方法可线性收敛于全局最优解。

Jun, 2015