Shannon Theoretic Limits on Noisy Compressive Sampling
| dc.creator | Akçakaya, Mehmet | |
| dc.creator | Tarokh, Vahid | |
| dc.date | 2007-11-02 | |
| dc.date.accessioned | 2026-07-07T08:40:16Z | |
| dc.date.available | 2026-07-07T08:40:16Z | |
| dc.description | In this paper, we study the number of measurements required to recover a sparse signal in ${\mathbb C}^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(L\log(M-L))$ measurements are required. We also show that $O(L\log(M-L))$ measurements are required in the sublinear regime ($L = o(M)$). | |
| dc.description | 21 pages, submitted | |
| dc.identifier | https://arxiv.org/abs/0711.0366 | |
| dc.identifier | http://arxiv.org/abs/0711.0366 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141325 | |
| dc.subject | Information Theory | |
| dc.subject | 94A12; 62B10 | |
| dc.title | Shannon Theoretic Limits on Noisy Compressive Sampling | |
| dc.type | text |