Imagine the vector y = Xβ + e where β ∈ ℝ m  has only k non zero entries and e ∈ 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 in (Wang et al., 2008).
['Kamiar Rahnama Rad']
Sharp upper bound on error probability of exact sparsity recovery