Fetching the paper…

Reading the bibliography…

2007

Shannon Theoretic Limits on Noisy Compressive Sampling

Akçakaya, Mehmet, Tarokh, Vahid

Original
PDF
Post on X

Understand

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)$).

Shannon Theoretic Limits on Noisy Compressive Sampling · Around

Built on

R. G. Gallager, Information Theory and Reliable Communication
1968
Earlier work this paper cites.
T. Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression
1971
Earlier work this paper cites.
L. Birgé and P. Massart, “Minimum Contrast Estimators on Sieves: Exponential Bounds and Rates of Convergence”, Bernoulli, vol. 4, no. 3, pp. 329-375, Sept. 1998
1998
Earlier work this paper cites.
B. Laurent and P. Massart, “Adaptive Estimation of a Quadratic Functional by Model Selection”, Annals of Statistics, vol. 28, no. 5, pp. 1303-1338, Oct. 2000
2000
Earlier work this paper cites.

Similar

B. Vucetic and J. Yuan, Space-Time Coding
2003
Cited alongside, same era.
J. A. Tropp, “Topics in Sparse Approximation”, Ph.D. dissertation, Computational and Applied Mathematics, UT-Austin, August 2004
2004
Cited alongside, same era.
E. J. Candès and T. Tao, “Decoding by Linear Programming”, IEEE Trans. on Inf. Theory, vol. 51, no. 12, pp. 4203-4215, Dec. 2005
2005
Cited alongside, same era.
M. Akçakaya and V. Tarokh, “A Frame Construction and A Universal Distortion Bound for Sparse Representations”, Accepted for publication in IEEE Trans. on Sig. Proc
Cited in the paper.

Then

D. L. Donoho, “Compressed Sensing”, IEEE Trans. on Inf. Theory, vol. 52, no. 4, pp. 1289-1306, April 2006
2006
Later among the works it cites.
M. J. Wainwright, “Sharp thresholds for noisy and high-dimensional recovery of sparsity using ℒ 1 {\cal L}_{1} -constrained quadratic programming”. Technical report, UC Berkeley, Department of Statistics, May 2006
2006
Later among the works it cites.
M. J. Wainwright, “Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting”, Technical Report, UC Berkeley, Department of Statistics, January 2007
2007
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…