The Stability of Low-Rank Matrix Reconstruction: A Constrained Singular Value View
The stability of low-rank matrix reconstruction with respect to noise is investigated in this paper. The l(*)-constrained minimal singular value (l(*)-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization-based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using l(*)-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have l(*)-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The l(*)-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of l(*)-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of l(*)-CMSV that is potentially useful for its computation.
l(*)-constrained minimal singular value (cmsv) correlated design matrix basis pursuit (mbp) matrix dantzig selector (mds) matrix lasso estimator (mlasso) restricted isometry property