Conference proceeding
Improved sparse recovery thresholds with two-step reweighted ℓ1 minimization
2010 IEEE International Symposium on Information Theory, pp.1603-1607
06/2010
DOI: 10.1109/ISIT.2010.5513417
Abstract
It is well known that ℓ 1 minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as "weak thresholds". In this paper, we introduce a reweighted ℓ 1 recovery algorithm composed of two steps: a standard ℓ 1 minimization step to identify a set of entries where the signal is likely to reside, and a weighted ℓ 1 minimization step where entries outside this set are penalized. For signals where the non-sparse component has iid Gaussian entries, we prove a "strict" improvement in the weak recovery threshold. Simulations suggest that the improvement can be quite impressive-over 20% in the example we consider.
Details
- Title: Subtitle
- Improved sparse recovery thresholds with two-step reweighted ℓ1 minimization
- Creators
- M Amin Khajehnejad - California Institute of TechnologyWeiyu Xu - Cornell UniversityA Salman Avestimehr - Cornell UniversityBabak Hassibi - California Institute of Technology
- Resource Type
- Conference proceeding
- Publication Details
- 2010 IEEE International Symposium on Information Theory, pp.1603-1607
- Publisher
- IEEE
- DOI
- 10.1109/ISIT.2010.5513417
- ISSN
- 2157-8095
- eISSN
- 2157-8117
- Language
- English
- Date published
- 06/2010
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984196967202771
Metrics
25 Record Views