Paper Info
Title
Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization
Abstract
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.
Year
DOI
Venue
2009
10.1007/s10208-011-9084-6
Foundations of Computational Mathematics
Keywords
DocType
Volume
Matrix rank minimization,Matrix completion,Greedy algorithm,Fixed-point method,Restricted isometry property,Singular value decomposition,90C59,15B52,15A18
Journal
11
Issue
ISSN
Citations 
2
1615-3375
49
PageRank 
References 
Authors
4.39
33
2
Name
Order
Citations
PageRank
Donald Goldfarb150030.02
Shiqian Ma2106863.48