Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
arXiv:1106.3276
Abstract
The low-rank matrix recovery (LMR) is a rank minimization problem subject to linear equality constraints, and it arises in many fields such as signal and image processing, statistics, computer vision, system identification and control. This class of optimization problems is -hard and a popular approach replaces the rank function with the nuclear norm of the matrix variable. In this paper, we extend the concept of -goodness for a sensing matrix in sparse signal recovery (proposed by Juditsky and Nemirovski [Math Program, 2011]) to linear transformations in LMR. Then, we give characterizations of -goodness in the context of LMR. Using the two characteristic -goodness constants, and , of a linear transformation, not only do we derive necessary and sufficient conditions for a linear transformation to be -good, but also provide sufficient conditions for exact and stable -rank matrix recovery via the nuclear norm minimization under mild assumptions. Moreover, we give computable upper bounds for one of the -goodness characteristics which leads to verifiable sufficient conditions for exact low-rank matrix recovery.
References in corpus (7)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
- On Verifiable Sufficient Conditions for Sparse Signal Recovery via Minimization
- Guaranteed Rank Minimization via Singular Value Projection
- Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint