Sharp upper bound on error probability of exact sparsity recovery

Imagine the vector y = Xbeta + epsi where beta isin Ropf^m has only k non zero entries and epsi isin Rⁿ is a Gaussian noise. This can be viewed as a linear system with sparsity constraints corrupted with noise. We find a non-asymptotic upper bound on the error probability of exact recovery of the sparsity pattern given any generic measurement matrix X. By drawing X from a Gaussian ensemble, as an example, to ensure exact recovery, we obtain asymptotically sharp sufficient conditions on n which meet the necessary conditions introduced in (Wang et al., 2008).