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
δk of the compressed sensing matrix satisfies
δk < 0.307, then k-sparse signals are guaranteed to be recovered exactly via l1 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
δ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 l1 minimization.
IEEE Transactions on Information Theory 55 , 3388-3397.