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

Abstract

The problem of recovering the sparsity pattern of a fixed but unknown vector ${\beta }^{\ast }\in {\Re }^{p}basedonasetof$n$noisyobservationsarisesinavarietyofsettings,includingsubsetselectioninregression,graphicalmodelselection,signaldenoising,compressivesensing,andconstructiveapproximation.Ofinterestareconditionsonthemodeldimension$p$,thesparsityindex$s$(numberofnon-zeroentriesin$β^*$),andthenumberofobservations$n$thatarenecessaryand/orsufficienttoensureasymptoticallyperfectrecoveryofthesparsitypattern.Thispaperfocusesontheinformation-theoreticlimitsofsparsityrecovery:inparticular,foranoisylinearobservationmodelbasedonmeasurementvectorsdrawnfromthestandardGaussianensemble,wederivebothasetofsufficientconditionsforasymptoticallyperfectrecoveryusingtheoptimaldecoder,aswellasasetofnecessaryconditionsthatanydecoder,regardlessofitscomputationalcomplexity,mustsatisfyforperfectrecovery.Thisanalysisofoptimaldecodinglimitscomplementsourpreviouswork(ARXIV:math.ST/0605740)onsharpthresholdsforsparsityrecoveryusingtheLasso($\ell_1$-constrained quadratic programming) with Gaussian measurement ensembles.

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

Cited by in corpus (6)

• Consistent selection via the Lasso for high dimensional approximating regression models
• Which graphical models are difficult to learn?
• Shannon Theoretic Limits on Noisy Compressive Sampling
• Compressive Sensing Using Low Density Frames
• Discussion: Latent variable graphical model selection via convex optimization
• Graph selection with GGMselect