Shannon-Theoretic Limits on Noisy Compressive Sampling

DOI10.1109/TIT.2009.2034796MaRDI QIDQ4976066zbMATH OpenOpenAlexFDO

Authors Mehmet Akçakaya, Vahid Tarokh

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/0711.0366

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Sampling theory in information and communication theory (94A20) Coding theorems (Shannon theory) (94A24)

Abstract: In this paper, we study the number of measurements required to recover a sparse signal in ${mathbbC}^M$ with $L$ non-zero coefficients from compressed samples in the presence of noise. For a number of different recovery criteria, we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements are necessary and sufficient if $L$ grows linearly as a function of $M$. This improves on the existing literature that is mostly focused on variants of a specific recovery algorithm based on convex programming, for which $O(Llog(M-L))$ measurements are required. We also show that $O(Llog(M-L))$ measurements are required in the sublinear regime ($L=o(M)$).

Cited in

(8)

• An evolutionary strategy based on partial imitation for solving optimization problems
• The all-or-nothing phenomenon in sparse linear regression
• 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
• Optimum Compression of a Noisy Measurement for Transmission Over a Noisy Channel
• Performance Limits of Segmented Compressive Sampling: Correlated Measurements Versus Bits
• High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective

This page was built for publication: Shannon-Theoretic Limits on Noisy Compressive Sampling

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