The DOI matches its Crossref record.
Necessary and Sufficient Conditions for Sparsity Pattern Recovery
Open accessAbstract
The paper considers the problem of detecting the sparsity pattern of a$k$-sparse vector in${\BBR }^{n}$from$m$random noisy measurements. A new necessary condition on the number of measurements for asymptotically reliable detection with maximum-likelihood (ML) estimation and Gaussian measurement matrices is derived. This necessary condition for ML detection is compared against a sufficient condition for simple maximum correlation (MC) or thresholding algorithms. The analysis shows that the gap between thresholding and ML can be described by a simple expression in terms of the total signal-to-noise ratio (SNR), with the gap growing with increasing SNR. Thresholding is also compared against the more sophisticated Lasso and orthogonal matching pursuit (OMP) methods. At high SNRs, it is shown that the gap between Lasso and OMP over thresholding is described by the range of powers of the nonzero component values of the unknown signals. Specifically, the key benefit of Lasso and OMP over thresholding is the ability of Lasso and OMP to detect signals with relatively small components.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Wainwright, M. J. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108627771 · Cited by 882
Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2032816 · Cited by 420
Harmless interpolation of noisy data in regression
Muthukumar, V., Vodrahalli, K., & Sahai, A. (2019) · 2019 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849614 · Cited by 162
Metadata
- Authors
- Fletcher, A. K., Rangan, S., & Goyal, V. K.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2009-12
- Volume
- 55
- Issue
- 12
- Pages
- 5758-5772
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W1674742109
- Cited by
- 224
- References
- 0
- FWCI
- 35.08
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Necessary and Sufficient Conditions for Sparsity Pattern Recovery. https://app.cochat.ai/papers/10.1109/tit.2009.2032726
- The paper
- Fletcher, A. K., Rangan, S., & Goyal, V. K. (2009). Necessary and Sufficient Conditions for Sparsity Pattern Recovery. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2009.2032726
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.