A Caltech Library Service

Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm

Khajehnejad, M. Amin and Xu, Weiyu and Avestimehr, A. Salman and Hassibi, Babak (2015) Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm. IEEE Transactions on Information Theory, 61 (9). pp. 5116-5128. ISSN 0018-9448.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 non-sparse 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper DOIArticle
Additional Information:© 2015 IEEE. Manuscript received November 6, 2011; revised April 9, 2015; accepted June 13, 2015. Date of publication June 23, 2015; date of current version August 14, 2015. This work was supported in part by the National Science Foundation under Grant CCF-0729203, Grant CNS-0932428, and Grant CCF-1018927, in part by the Office of Naval Research within the Multidisciplinary University Research Initiative under Grant N00014-08-1-0747, and in part by the Caltech’s Lee Center for Advanced Networking. W. Xu was supported in part by the Simons Foundation and in part by the Iowa Energy Center. This paper was presented at the International Symposium on Information Theory in 2010.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Simons FoundationUNSPECIFIED
Iowa Energy CenterUNSPECIFIED
Subject Keywords:Iterative reweighted, compressed sensing, basis pursuit, phase transition
Issue or Number:9
Record Number:CaltechAUTHORS:20150127-072715568
Persistent URL:
Official Citation:Khajehnejad, M.A.; Xu, W.; Avestimehr, A.S.; Hassibi, B., "Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm," Information Theory, IEEE Transactions on , vol.61, no.9, pp.5116,5128, Sept. 2015 doi: 10.1109/TIT.2015.2448690
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54111
Deposited By: Shirley Slattery
Deposited On:28 Jan 2015 00:02
Last Modified:03 Oct 2019 07:55

Repository Staff Only: item control page