A note on guaranteed sparse recovery via ℓ1-minimization

It is proved that every s-sparse vector x∈CN can be recovered from the measurement vector y=Ax∈Cm via ℓ1-minimization as soon as the 2s-th restricted isometry constant of the matrix A is smaller than , or smaller than for large values of s.