The stability of low-rank matrix reconstruction: A constrained singular value perspective

The stability of low-rank matrix reconstruction is investigated in this paper. The ℓ_*-constrained minimal singular value (ℓ_*-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 ℓ_*-CMSV are more concise and tight, and their derivations are less complex. Several random measurement ensembles are shown to have ℓ_*-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large.