Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting

Details Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting

2007-02-11

arxiv.org/abs/math/0702301v2

Mathematics

Statistics Theory

Appeared as Technical Report 725, Department of Statistics, UC Berkeley January 2007

Scientific paper

The problem of recovering the sparsity pattern of a fixed but unknown vector $\beta^* \in \real^p based on a set of $n$ noisy observations arises in a variety of settings, including subset selection in regression, graphical model selection, signal denoising, compressive sensing, and constructive approximation. Of interest are conditions on the model dimension $p$, the sparsity index $s$ (number of non-zero entries in $\beta^*$), and the number of observations $n$ that are necessary and/or sufficient to ensure asymptotically perfect recovery of the sparsity pattern. This paper focuses on the information-theoretic limits of sparsity recovery: in particular, for a noisy linear observation model based on measurement vectors drawn from the standard Gaussian ensemble, we derive both a set of sufficient conditions for asymptotically perfect recovery using the optimal decoder, as well as a set of necessary conditions that any decoder, regardless of its computational complexity, must satisfy for perfect recovery. This analysis of optimal decoding limits complements our previous work (ARXIV: math.ST/0605740) on sharp thresholds for sparsity recovery using the Lasso ($\ell_1$-constrained quadratic programming) with Gaussian measurement ensembles.

Affiliated with

Also associated with

No associations

Rating

Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-538801