Title
Sparse Signal Processing With Linear And Non-Linear Observations: A Unified Shannon Theoretic Approach
Abstract
In this work we derive fundamental limits for many linear and non-linear sparse signal processing models including group testing, quantized compressive sensing, multivariate regression and observations with missing features. In general, sparse signal processing problems can be characterized in terms of the following Markovian property. We are given a set of N variables X1, Χ2,..., Xn, and there is an unknown subset of variables S ⊂ {1, 2,..., N} that are relevant for predicting outcomes/outputs Y. In other words, when Y is conditioned on {X n}nS it is conditionally independent of the other variables, {Xn}nS. Our goal is to identify the set S from samples of the variables X and the associated outcomes Y. We characterize this problem as a version of the noisy channel coding problem. Using asymptotic information theoretic analyses, we establish mutual information formulas that provide sufficient and necessary conditions on the number of samples required to successfully recover the salient variables. These mutual information expressions unify conditions for both linear and non-linear observations. We then compute sample complexity bounds for the aforementioned models, based on the mutual information expressions. © 2013 IEEE.
Publication Date
12-1-2013
Publication Title
2013 IEEE Information Theory Workshop, ITW 2013
Number of Pages
-
Document Type
Article; Proceedings Paper
Personal Identifier
scopus
DOI Link
https://doi.org/10.1109/ITW.2013.6691346
Copyright Status
Unknown
Socpus ID
84893310378 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/84893310378
STARS Citation
Aksoylar, Cem; Atia, George; and Saligrama, Venkatesh, "Sparse Signal Processing With Linear And Non-Linear Observations: A Unified Shannon Theoretic Approach" (2013). Scopus Export 2010-2014. 5834.
https://stars.library.ucf.edu/scopus2010/5834