Compressed Sensing and Affine Rank Minimization Under Restricted Isometry

This paper establishes new restricted isometry conditions for compressed sensing and affine rank minimization. It is shown for compressed sensing thatδₖA+θk, kA < 1guarantees the exact recovery of allksparse signals in the noiseless case through the constrained₁minimization. Furthermore, the upper bound 1 is sharp in the sense that for anyε > 0, the conditionδₖA + θk, kA < 1+εis not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, ifδᵣ^ M+θr, r^ M < 1then all matrices with rank at mostrcan be reconstructed exactly in the noiseless case via the constrained nuclear norm minimization; and for anyε > 0,δ_r^{{ M}} +θr, r^{{ M}} < 1+ε$does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions$δₖA+θk, kA < 1$and$δᵣ^{{ M}}+θr, r^{{ M}} < 1$are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.