New Bounds for Restricted Isometry Constants

Abstract

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 δ_k of Φ satisfies δ_k <; 0.307 then k-sparse signals are guaranteed to be recovered exactly via ℓ₁ 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 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.