Necessary and Sufficient Conditions for Sparsity Pattern Recovery
he 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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52487 |
| _version_ | 1826194394094501888 |
|---|---|
| author | Fletcher, Alyson K. Goyal, Vivek K. Rangan, Sundeep |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Fletcher, Alyson K. Goyal, Vivek K. Rangan, Sundeep |
| author_sort | Fletcher, Alyson K. |
| collection | MIT |
| description | he 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. |
| first_indexed | 2024-09-23T09:55:26Z |
| format | Article |
| id | mit-1721.1/52487 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:55:26Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/524872022-09-30T17:42:42Z Necessary and Sufficient Conditions for Sparsity Pattern Recovery Fletcher, Alyson K. Goyal, Vivek K. Rangan, Sundeep Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Goyal, Vivek K. Fletcher, Alyson K. Goyal, Vivek K. he 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. Centre Bernoulli at École Polytechnique Fédérale de Lausanne National Science Foundation (CAREER Grant CCF-643836) University of California President’s Postdoctoral Fellowship 2010-03-10T20:33:17Z 2010-03-10T20:33:17Z 2009-11 2009-02 Article http://purl.org/eprint/type/JournalArticle 0018-9448 http://hdl.handle.net/1721.1/52487 Fletcher, A.K., S. Rangan, and V.K. Goyal. “Necessary and Sufficient Conditions for Sparsity Pattern Recovery.” Information Theory, IEEE Transactions on 55.12 (2009): 5758-5772. © 2009 IEEE en_US http://dx.doi.org/10.1109/tit.2009.2032726 IEEE Transactions on Information Theory Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Fletcher, Alyson K. Goyal, Vivek K. Rangan, Sundeep Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title | Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title_full | Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title_fullStr | Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title_full_unstemmed | Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title_short | Necessary and Sufficient Conditions for Sparsity Pattern Recovery |
| title_sort | necessary and sufficient conditions for sparsity pattern recovery |
| url | http://hdl.handle.net/1721.1/52487 |
| work_keys_str_mv | AT fletcheralysonk necessaryandsufficientconditionsforsparsitypatternrecovery AT goyalvivekk necessaryandsufficientconditionsforsparsitypatternrecovery AT rangansundeep necessaryandsufficientconditionsforsparsitypatternrecovery |