Tight Sufficient Conditions on Exact Sparsity Pattern Recovery

2012/09/19 by Behrooz Kamary Aliabadi, Aliabadi, Behrooz Kamary, Silèye Ba +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1209.4209

arxiv created 2014/06/25 · arxiv updated 2014/06/26

Abstract

A noisy underdetermined system of linear equations is considered in which a sparse vector (a vector with a few nonzero elements) is subject to measurement. The measurement matrix elements are drawn from a Gaussian distribution. We study the information-theoretic constraints on exact support recovery of a sparse vector from the measurement vector and matrix. We compute a tight, sufficient condition that is applied to ergodic wide-sense stationary sparse vectors. We compare our results with the existing bounds and recovery conditions. Finally, we extend our results to approximately sparse signals.

Related

• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices
• Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
• An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting