New Bounds for Restricted Isometry Constants

Tony Cai, Lie Wang and Guangwu Xu

---

• Abstract: In this paper we show that if the restricted isometry constant &delta_k of the compressed sensing matrix satisfies
  &delta_k < 0.307, then k-sparse signals are guaranteed to be recovered exactly via l₁ minimization when no noise is present and k-sparse signals can be estimated stably in the noisy case. It is also shown that the bound cannot be substantively improved. An explicitly example is constructed in which
  &delta_k = (k-1)/(2k-1) < 0.5, but it is impossible to recover certain k-sparse signals.

• Paper: pdf file.

• Other related papers:

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

  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., Xu, G. & Zhang, J. (2009).
  On recovery of sparse signals via l₁ minimization.
  IEEE Transactions on Information Theory 55 , 3388-3397.