On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization

Anatoli Juditsky, Arkadii S. Nemirovski

We propose novel necessary and sufficient conditions for a sensing matrix to be "$s$-good" - to allow for exact ${\ell }_1$-recovery of sparse signals with $s$ nonzero entries when no…