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 $ell _{ast}$-constrained minimal singular value ( $ell _{ast}$-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 $ell _{ast}$-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have $ell _{ast}$-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The $ell _{ast}$-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of $ell _{ast}$-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of $ell _{ast}$-CMSV that is potentially useful for its computation.