Information Theoretic Bounds for Compressed Sensing

DOI10.1109/TIT.2010.2059891MaRDI QIDQ5281264zbMATH OpenFDO

Authors Shuchin Aeron, Venkatesh Saligrama, Manqi Zhao

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0804.3439

Mathematics Subject Classification ID

Information theory (general) (94A15) Measures of information, entropy (94A17) Rate-distortion theory in information and communication theory (94A34)

Abstract: In this paper we derive information theoretic performance bounds to sensing and reconstruction of sparse phenomena from noisy projections. We consider two settings: output noise models where the noise enters after the projection and input noise models where the noise enters before the projection. We consider two types of distortion for reconstruction: support errors and mean-squared errors. Our goal is to relate the number of measurements, $m$, and $snr$, to signal sparsity, $k$, distortion level, $d$, and signal dimension, $n$. We consider support errors in a worst-case setting. We employ different variations of Fano's inequality to derive necessary conditions on the number of measurements and $snr$ required for exact reconstruction. To derive sufficient conditions we develop new insights on max-likelihood analysis based on a novel superposition property. In particular this property implies that small support errors are the dominant error events. Consequently, our ML analysis does not suffer the conservatism of the union bound and leads to a tighter analysis of max-likelihood. These results provide order-wise tight bounds. For output noise models we show that asymptotically an $snr$ of $Theta(log(n))$ together with $Theta(klog(n/k))$ measurements is necessary and sufficient for exact support recovery. Furthermore, if a small fraction of support errors can be tolerated, a constant $snr$ turns out to be sufficient in the linear sparsity regime. In contrast for input noise models we show that support recovery fails if the number of measurements scales as $o(nlog(n)/SNR)$ implying poor compression performance for such cases. We also consider Bayesian set-up and characterize tradeoffs between mean-squared distortion and the number of measurements using rate-distortion theory.

Cited in

(20)

• A strong converse bound for multiple hypothesis testing, with applications to high-dimensional estimation
• The all-or-nothing phenomenon in sparse linear regression
• Iterative algorithm for discrete structure recovery
• Adaptive multi-penalty regularization based on a generalized Lasso path
• Which bridge estimator is the best for variable selection?
• Fano's inequality for random variables
• Non-uniform recovery guarantees for binary measurements and infinite-dimensional compressed sensing
• Compressed Sensing with Side Information on the Feasible Region
• Sparse microwave imaging: principles and applications
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Compressed Sensing Performance Bounds Under Poisson Noise
• Asymptotic Achievability of the CramÉr–Rao Bound for Noisy Compressive Sampling
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
• Computational approaches to non-convex, sparsity-inducing multi-penalty regularization
• Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression
• Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices
• Numerical characterization of support recovery in sparse regression with correlated design
• Robust multitask feature learning with adaptive Huber regressions
• High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective
• Rigorous restricted isometry property of low-dimensional subspaces

This page was built for publication: Information Theoretic Bounds for Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281264)