Enhancing Sparsity by Reweighted ℓ1 Minimization

By E.J. Candes, Michael B. Wakin, Stephen P. Boyd. 2007

5,262 citations recorded by the source corpus.

It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained ℓ1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms ℓ1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted ℓ1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the ℓ1 norm of the coefficient sequence as is common, but by reweighting the ℓ1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

  1. E.J. Candes
  2. Yonina C. Eldar
  3. Justin K. Romberg
  4. Gitta Kutyniok
  5. Zhouchen Lin
  6. René Vidal
  7. Shuicheng Yan
  8. Bhaskar D. Rao

In Computational Mechanics

  1. Lei Zhang
  2. Francis R. Bach
  3. Julien Mairal
  4. E.J. Candes
  5. Wangmeng Zuo
  6. Wotao Yin
  7. Zhouchen Lin
  8. Shuicheng Yan

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Lei Zhang
  3. Dacheng Tao
  4. Ming-Hsuan Yang
  5. Xiaogang Wang
  6. Chen Change Loy
  7. Yi Yang
  8. Trevor Darrell

Citations in the corpus