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

Socpus ID

84893310378 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84893310378

This document is currently not available here.

Share

COinS