Journal
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
Volume 11, Issue 2, Pages 183-210Publisher
SPRINGER
DOI: 10.1007/s10208-011-9084-6
Keywords
Matrix rank minimization; Matrix completion; Greedy algorithm; Fixed-point method; Restricted isometry property; Singular value decomposition
Funding
- NSF [DMS 06-06712, DMS 10-16571]
- ONR [N00014-03-0514, N00014-08-1-1118]
- DOE [DE-FG01-92ER-25126, DE-FG02-08ER-25856]
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1016571] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available