Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery

Consider the $n$-dimensional vector $y=X\text{be}+\text{e}$, where $\text{be}\in {\mathbb{R}}^p$ has only $k$ nonzero entries and $\text{e}\in {\mathbb{R}}^n$ is a Gaussian noise. This can be viewed as a linear system with sparsity constraints, corrupted by noise. We find a non-asymptotic upper bound on the probability that the optimal decoder for $\beta$ declares a wrong sparsity pattern, given any generic perturbation matrix $X$. In the case when $X$ is randomly drawn from a Gaussian ensemble, we obtain asymptotically sharp sufficient conditions for exact recovery, which agree with the known necessary conditions previously established.