Improved sparse recovery thresholds with two-step reweighted ℓ_1 minimization
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" [4]. 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.
Additional Information
© 2010 IEEE. Issue Date: 13-18 June 2010, Date of Current Version: 23 July 2010.Attached Files
Published - Khajehnejad2010p132612010_Ieee_International_Symposium_On_Information_Theory.pdf
Submitted - 1004.0402.pdf
Files
Name | Size | Download all |
---|---|---|
md5:d1ed5a15da0f9cfb205cef54548ce882
|
242.3 kB | Preview Download |
md5:6e0f670e261eca4799ad9397c085170a
|
163.9 kB | Preview Download |
Additional details
- Eprint ID
- 23156
- Resolver ID
- CaltechAUTHORS:20110329-105653717
- Created
-
2011-03-29Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- IEEE International Symposium on Information Theory