2011/11/06 by M. Amin Khajehnejad, Khajehnejad, M. Amin, Weiyu Xu +5
Engineering · Medicine · #Advanced MRI Techniques and Applications #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1111.1396
openalex publication_date 2011/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that \ℓ1 minimization can be used to recover\nsufficiently sparse unknown signals from compressed linear measurements. In\nfact, exact thresholds on the sparsity, as a function of the ratio between the\nsystem dimensions, so that with high probability almost all sparse signals can\nbe recovered from i.i.d. Gaussian measurements, have been computed and are\nreferred to as "weak thresholds" citeD. In this paper, we introduce a\nreweighted \ℓ1 recovery algorithm composed of two steps: a standard\n\ℓ1 minimization step to identify a set of entries where the signal is\nlikely to reside, and a weighted \ℓ1 minimization step where entries\noutside this set are penalized. For signals where the non-sparse component\nentries are independent and identically drawn from certain classes of\ndistributions, (including most well known continuous distributions), we prove a\n\strict improvement in the weak recovery threshold. Our analysis suggests\nthat the level of improvement in the weak threshold depends on the behavior of\nthe distribution at the origin. Numerical simulations verify the distribution\ndependence of the threshold improvement very well, and suggest that in the case\nof i.i.d. Gaussian nonzero entries, the improvement can be quite\nimpressive---over 20% in the example we consider.\n