It is shown that for any given constant t ≥ 4/3, in compressed sensing δ^A_tk < √ (t-1)/t  guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l₁ minimization, and similarly in affine rank minimization δ^M_tk < √ (t-1)/t  ensures the exact reconstruction of all matrices with rank at most r in the noiseless case via the constrained nuclear norm minimization. Moreover, for any ε > 0, δ^A_tk < √ (t-1)/t  + ε is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar result also holds for matrix recovery. In addition, the conditions δ^A_tk < √ (t-1)/t  and δ^M_tr < √ (t-1)/t  are also shown to be sufficient respectively for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.

Cai, T. & Zhang, A. (2013).
Compressed sensing and affine rank minimization under restricted isometry.
IEEE Transactions on Signal Processing 61, 3279-3290.

Cai, T. & Zhang, A. (2013).
Sharp RIP bound for sparse signal and low-rank matrix recovery.
Applied and Computational Harmonic Analysis 35, 74-93.

Cai, T., Wang, L. & Xu, G. (2010).
New Bounds for Restricted Isometry Constants.
IEEE Transactions on Information Theory 56, 4388-4394.

Cai, T., Wang, L. & Xu, G. (2010).
Stable recovery of sparse signals and an oracle inequality.
IEEE Transactions on Information Theory 56, 3516-3522.

Cai, T., Wang, L. & Xu, G. (2010).
Shifting inequality and recovery of sparse signals.
IEEE Transactions on Signal Processing 58, 1300-1308.

Cai, T., Xu, G. & Zhang, J. (2009).
On recovery of sparse signals via l₁ minimization.
IEEE Transactions on Information Theory 55, 3388-3397.