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_{k}^{A}+\theta_{k, k}^{A} < 1$
guarantees the exact recovery of all
$k$
sparse signals in the noiseless case through the constrained
$\ell_1$
minimization. Furthermore, the upper bound 1 is sharp in the sense that for any
$\epsilon > 0$
, the condition
$\delta_k^{A} + \theta_{k, k}^{A} < 1+\epsilon$
is not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, if
$\delta_{r}^{{\cal M}}+\theta_{r, r}^{{\cal M}} < 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_r^{{\cal M}} +\theta_{r, r}^{{\cal M}} < 1+\epsilon$
does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions
$\delta_{k}^{A}+\theta_{k, k}^{A} < 1$
and
$\delta_{r}^{{\cal M}}+\theta_{r, r}^{{\cal M}} < 1$
are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.