Computer Science – Information Theory
Scientific paper
2010-04-02
Computer Science
Information Theory
accepted in ISIT 2010
Scientific paper
It is well known that $\ell_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" \cite{D}. In this paper, we introduce a reweighted $\ell_1$ recovery algorithm composed of two steps: a standard $\ell_1$ minimization step to identify a set of entries where the signal is likely to reside, and a weighted $\ell_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.
Avestimehr Salman
Hassibi Babak
Khajehnejad Amin M.
Xu Weiyu
No associations
LandOfFree
Improved Sparse Recovery Thresholds with Two-Step Reweighted $\ell_1$ Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Sparse Recovery Thresholds with Two-Step Reweighted $\ell_1$ Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Sparse Recovery Thresholds with Two-Step Reweighted $\ell_1$ Minimization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-198457