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

Martin J. Wainwright

paper

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

arXiv:math/0702301

Abstract

The problem of recovering the sparsity pattern of a fixed but unknown vector $β^{*} \in ℜ^{p} ba se d o na se t o f$ n $n o i sy o b ser v a t i o n s a r i ses ina v a r i e t y o f se tt in g s, in c l u d in g s u b se t se l ec t i o nin r e g r ess i o n, g r a p hi c a l m o d e l se l ec t i o n, s i g na l d e n o i s in g, co m p r ess i v ese n s in g, an d co n s t r u c t i v e a pp r o x ima t i o n . O f in t er es t a r eco n d i t i o n so n t h e m o d e l d im e n s i o n$ p $, t h es p a r s i t y in d e x$ s $(n u mb er o f n o n - z er oe n t r i es in$ β^* $), an d t h e n u mb er o f o b ser v a t i o n s$ n $t ha t a r e n ecess a r y an d / or s u f f i c i e n tt oe n s u r e a sy m pt o t i c a l l y p er f ec t r eco v er y o f t h es p a r s i t y p a tt er n . T hi s p a p er f oc u seso n t h e in f or ma t i o n - t h eor e t i c l imi t so f s p a r s i t y r eco v er y : in p a r t i c u l a r, f or an o i sy l in e a r o b ser v a t i o nm o d e l ba se d o nm e a s u r e m e n t v ec t or s d r a w n f r o m t h es t an d a r d G a u ss ian e n se mb l e, w e d er i v e b o t ha se t o f s u f f i c i e n t co n d i t i o n s f or a sy m pt o t i c a l l y p er f ec t r eco v er y u s in g t h eo pt ima l d eco d er, a s w e l l a s a se t o f n ecess a r y co n d i t i o n s t ha t an y d eco d er, r e g a r d l esso f i t sco m p u t a t i o na l co m pl e x i t y, m u s t s a t i s f y f or p er f ec t r eco v er y . T hi s ana l y s i so f o pt ima l d eco d in g l imi t sco m pl e m e n t so u r p r e v i o u s w or k (A R X I V : ma t h . S T /0605740) o n s ha r pt h r es h o l d s f or s p a r s i t y r eco v er y u s in g t h e L a sso ($ \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 (1)

Shannon Theoretic Limits on Noisy Compressive Sampling