New Bounds for Restricted Isometry Constants

This paper discusses new bounds for restricted isometry constants in compressed sensing. Let Φ be an n × p real matrix and A; be a positive integer with k ≤ n. One of the main results of this paper shows that if the restricted isometry constant δkof Φ satisfies δk1minimization 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 substantially improved. An explicit example is constructed in which δk= k-1/2k-1 <; 0.5, but it is impossible to recover certain k-sparse signals.