A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
Qinqing Zheng John Lafferty University of Chicago
Abstract
We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With $O(r^{3}\kappa^{2}n\log n)$ random measurements of a positive semidefinite $n\times n$ matrix of rank $r$ and condition number $\kappa$ , our method is guaranteed to converge linearly to the global optimum.
中文速览
低秩矩阵恢复（rank minimization）和半正定规划（semidefinite programming, SDP）在机器学习、信号处理等领域极为重要，但现有方法要么依赖代价高昂的奇异值分解，要么难以扩展到大规模问题。针对这一困境，作者提出了一种简单的梯度下降算法：先用谱方法做初始化，再对非凸目标函数直接做梯度迭代，将问题转化为对因子矩阵 Z 的优化，完全避免了每轮迭代的 SVD 计算。理论上，只需 O(r³κ²n log n) 次随机测量，算法就能以线性收敛速度精确恢复目标矩阵，其中 r 为秩、κ 为条件数、n 为矩阵维度；实验还表明，当测量矩阵稀疏时，该方法的速度优势尤为突出。这项工作填补了大规模 SDP 与秩最小化问题在理论保证与实际效率之间长期存在的鸿沟，也将相位恢复领域的 Wirtinger Flow 框架推广到了更一般的矩阵恢复场景。
原文 arXiv:1506.06081;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1506.06081v3