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

Simple item page
dc.creatorWainwright, Martin J.
dc.date2007-02-11
dc.date2007-02-20
dc.date.accessioned2026-07-07T08:17:12Z
dc.date.available2026-07-07T08:17:12Z
dc.descriptionThe problem of recovering the sparsity pattern of a fixed but unknown vector $β^* \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 $β^*$), 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.
dc.descriptionAppeared as Technical Report 725, Department of Statistics, UC Berkeley January 2007
dc.identifierhttps://arxiv.org/abs/math/0702301
dc.identifierhttp://arxiv.org/abs/math/0702301
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134044
dc.subjectStatistics Theory
dc.subjectInformation Theory
dc.titleInformation-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
dc.typetext

Files

Collections

arXiv