Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization
Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization
复制标题
DOI：
10.1007/s10208-011-9084-6
复制
发表时间：
2011-04-01
影响因子：
3
通讯作者：
Ma, Shiqian
中科院分区：
文献类型：
--
作者：
Goldfarb, Donald;Ma, Shiqian
矩阵秩最小化问题在系统辨识、最优控制、低维嵌入等领域有着广泛的应用。由于该问题一般是NP-困难的，因此其凸松弛问题，即核范数最小化问题，常常被用来代替求解。最近，Ma，Goldfarb和Chen提出了一种用于求解核范数最小化问题的不动点连续算法（Math. Program.，doi：10.1007/s10107-009-0306-5，2009）。该算法通过引入一种近似奇异值分解技术，通常可以得到矩阵秩最小化问题的解。本文研究了矩阵秩最小化问题的不动点连续算法及其变形的收敛性和可恢复性。启发式确定矩阵的秩时，其真实的秩是未知的也提出了。其中一些算法与压缩感知中的贪婪算法密切相关。报告了这些算法求解仿射约束矩阵秩最小化问题的数值结果。
The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:10.1007/s10107-009-0306-5, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.