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