An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

By Ingrid Daubechies, Michel Defrise, Christine De Mol. 2003

5,379 citations recorded by the source corpus.

We consider linear inverse problems where the solution is assumed to have a sparse expansion on an arbitrary preassigned orthonormal basis. We prove that replacing the usual quadratic regularizing penalties by weighted 𝓁p‐penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem. Use of such 𝓁p‐penalized problems with p < 2 is often advocated when one expects the underlying ideal noiseless solution to have a sparse expansion with respect to the basis under consideration. To compute the corresponding regularized solutions, we analyze an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm. © 2004 Wiley Periodicals, Inc.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, Mathematical Optimization, Numerical Methods & Scientific Computing

How researchers see this paper

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

In Computational Mechanics

  1. Francis R. Bach
  2. Julien Mairal
  3. Lei Zhang
  4. E.J. Candes
  5. Wotao Yin
  6. Peter Richtárik
  7. Richard Baraniuk
  8. Stephen P. Boyd

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Lei Zhang
  3. Dacheng Tao
  4. Ming-Hsuan Yang
  5. Trevor Darrell
  6. Xiaogang Wang
  7. Jitendra Malik
  8. Andrew Zisserman

In Mathematical Physics

  1. Stephen P. Boyd
  2. Wotao Yin
  3. Thomas Pock
  4. Francis R. Bach
  5. Lei Zhang
  6. Stanley J. Osher
  7. Laurent Condat
  8. Antonin Chambolle

In Mathematical Optimization

  1. Julien Mairal
  2. Francis R. Bach
  3. Robert Tibshirani
  4. Paul Tseng
  5. Tong Zhang
  6. Stephen P. Boyd
  7. Thomas Pock
  8. Wotao Yin

In Numerical Methods & Scientific Computing

  1. Julien Mairal
  2. E.J. Candes
  3. Lei Zhang
  4. Thomas Pock
  5. Francis R. Bach
  6. Richard Baraniuk
  7. Gitta Kutyniok
  8. Mário A. T. Figueiredo

Citations in the corpus