Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery

2009/10/02 by Rad, Kamiar Rahnama · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.0910.0456

Abstract

Consider the n-dimensional vector y=X\be+\e, where \be ∈ \R^p has only k nonzero entries and \e ∈ \Rⁿ 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 β 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.

Cited by

• Optimality and computational barriers in variable selection under dependence

Related

• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Tight Sufficient Conditions on Exact Sparsity Pattern Recovery
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency
• Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model