Sharp Upper Bound on Error Probability of Exact Sparsity Recovery

Abstract-Imagine the vector y = Xβ + where β ∈ R m has only k non zero entries and ∈ R n 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 i