CaltechAUTHORS
  A Caltech Library Service

Improved sparse recovery thresholds with two-step reweighted ℓ_1 minimization

Khajehnejad, M. Amin and Xu, Weiyu and Avestimehr, A. Salman and Hassibi, Babak (2010) Improved sparse recovery thresholds with two-step reweighted ℓ_1 minimization. In: 2010 IEEE International Symposium on Information Theory. IEEE International Symposium on Information Theory . IEEE , Piscataway, NJ, pp. 1603-1607. ISBN 978-1-4244-7891-0. https://resolver.caltech.edu/CaltechAUTHORS:20110329-105653717

[img]
Preview
PDF - Published Version
See Usage Policy.

236Kb
[img] PDF - Submitted Version
See Usage Policy.

160Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110329-105653717

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2010.5513417DOIArticle
https://arxiv.org/abs/1004.0402arXivDiscussion Paper
Additional Information:© 2010 IEEE. Issue Date: 13-18 June 2010, Date of Current Version: 23 July 2010.
Series Name:IEEE International Symposium on Information Theory
Record Number:CaltechAUTHORS:20110329-105653717
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20110329-105653717
Official Citation:M. A. Khajehnejad, W. Xu, A. S. Avestimehr and B. Hassibi, "Improved sparse recovery thresholds with two-step reweighted ℓ1 minimization," 2010 IEEE International Symposium on Information Theory, Austin, TX, 2010, pp. 1603-1607. doi: 10.1109/ISIT.2010.5513417
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23156
Collection:CaltechAUTHORS
Deposited By: Benjamin Perez
Deposited On:29 Mar 2011 20:12
Last Modified:03 Oct 2019 02:44

Repository Staff Only: item control page