Skip to main content

Approximate sparsity pattern recovery: Information-theoretic lower bounds

Publication ,  Journal Article
Reeves, G; Gastpar, MC
Published in: IEEE Transactions on Information Theory
May 23, 2013

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear measurements is an important problem in compressed sensing. In this paper, the high-dimensional setting is considered. It is shown that if the measurement rate and per-sample signal-to-noise ratio (SNR) are finite constants independent of the length of the vector, then the optimal sparsity pattern estimate will have a constant fraction of errors. Lower bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector. The tightness of the bounds in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing achievable bounds. Near optimality is shown for a wide variety of practically motivated signal models. © 1963-2012 IEEE.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

May 23, 2013

Volume

59

Issue

6

Start / End Page

3451 / 3465

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reeves, G., & Gastpar, M. C. (2013). Approximate sparsity pattern recovery: Information-theoretic lower bounds. IEEE Transactions on Information Theory, 59(6), 3451–3465. https://doi.org/10.1109/TIT.2013.2253852
Reeves, G., and M. C. Gastpar. “Approximate sparsity pattern recovery: Information-theoretic lower bounds.” IEEE Transactions on Information Theory 59, no. 6 (May 23, 2013): 3451–65. https://doi.org/10.1109/TIT.2013.2253852.
Reeves G, Gastpar MC. Approximate sparsity pattern recovery: Information-theoretic lower bounds. IEEE Transactions on Information Theory. 2013 May 23;59(6):3451–65.
Reeves, G., and M. C. Gastpar. “Approximate sparsity pattern recovery: Information-theoretic lower bounds.” IEEE Transactions on Information Theory, vol. 59, no. 6, May 2013, pp. 3451–65. Scopus, doi:10.1109/TIT.2013.2253852.
Reeves G, Gastpar MC. Approximate sparsity pattern recovery: Information-theoretic lower bounds. IEEE Transactions on Information Theory. 2013 May 23;59(6):3451–3465.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

May 23, 2013

Volume

59

Issue

6

Start / End Page

3451 / 3465

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing