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 δ<;i>kA<;/i>+θ<;i>k<;/i>,<;i>kA<;/i> <; 1 guarantees the exact recovery of all <;i>k<;/i> sparse signals in the noiseless case through the constrained <;i>l<;/i><;sub>1<;/sub> minimization. Furthermore, the upper bound 1 is sharp in the sense that for any ε > 0, the condition δ<;i>kA<;/i> + θ<;i>k<;/i>,<;i>kA<;/i> <; 1+ε is not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, if δ<;i>rM<;/i>+θ<;i>r<;/i>,<;i>rM<;/i> <; 1 then all matrices with rank at most <;i>r<;/i> can be reconstructed exactly in the noiseless case via the constrained nuclear norm minimization; and for any ε > 0, δ<;i>rM<;/i> +θ<;i>r<;/i>,<;i>rM<;/i> <; 1+ε does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions δ<;i>kA<;/i>+θ<;i>k<;/i>,<;i>kA<;/i> <; 1 and δ<;i>rM<;/i>+θ<;i>r<;/i>,<;i>rM<;/i> <; 1 are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.