An optimization-based multilevel algorithm for total variation image denoising

Tony F. Chan, Ke Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

69 Scopus citations


This paper proposes a fast multilevel method using primal relaxations for the total variation image denoising and analyzes its convergence. The basic primal relaxation is known to get stuck at a nonstationary point (nearly a local minimum) of the minimization, whose solution is known to be "nonsmooth" in the space of functions with bounded variation. Our idea is to use coarse level corrections, overcoming the deadlock in a basic primal relaxation scheme and achieving much improvement over relaxation. Moreover, to reach a global minimizer, further refinement of the multilevel method is needed, and we propose a nonregular coarse level based on a patch-detection idea (relating to hemivariateness) to correct and improve the standard multilevel method. Both algorithmic and analytical results together with numerical experiments on both one- and two-dimensional images are presented.

Original languageEnglish (US)
Pages (from-to)615-645
Number of pages31
JournalMultiscale Modeling and Simulation
Issue number2
StatePublished - May 2006
Externally publishedYes


  • Global convergence
  • Hemivariateness
  • Image restoration
  • Multilevel solvers
  • Nondifferentiability
  • Optimization
  • Primal relaxation
  • Regularization
  • Total variation

ASJC Scopus subject areas

  • General Chemistry
  • Modeling and Simulation
  • Ecological Modeling
  • General Physics and Astronomy
  • Computer Science Applications


Dive into the research topics of 'An optimization-based multilevel algorithm for total variation image denoising'. Together they form a unique fingerprint.

Cite this