Journal article
Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm
IEEE transactions on information theory, Vol.61(9), pp.5116-5128
09/2015
DOI: 10.1109/TIT.2015.2448690
Abstract
It is well known that ℓ 1 minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. 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 independent identically distributed (i.i.d.) 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: 1) a standard ℓ 1 minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted ℓ 1 minimization step where entries outside this set are penalized. For signals where the nonsparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive-over 20% in the example we consider.
Details
- Title: Subtitle
- Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm
- Creators
- M. Amin Khajehnejad - California Institute of TechnologyWeiyu Xu - University of IowaA. Salman Avestimehr - University of Southern CaliforniaBabak Hassibi - California Institute of Technology
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on information theory, Vol.61(9), pp.5116-5128
- DOI
- 10.1109/TIT.2015.2448690
- ISSN
- 0018-9448
- eISSN
- 1557-9654
- Publisher
- IEEE
- Grant note
- Simons Foundation (10.13039/100000893) N00014-08-1-0747 / Office of Naval Research within the Multidisciplinary University Research Initiative CCF-0729203; CNS-0932428; CCF-1018927 / National Science Foundation (10.13039/100000001) Caltech’s Lee Center for Advanced Networking Iowa Energy Center
- Language
- English
- Date published
- 09/2015
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197064102771
Metrics
16 Record Views