Analysis of Half-Quadratic Minimization Methods for Signal and Image Recovery

Mila Nikolova, Michael K. Ng

Research output: Contribution to journalJournal articlepeer-review

376 Citations (Scopus)
85 Downloads (Pure)

Abstract

We address the minimization of regularized convex cost functions which are customarily used for edge-preserving restoration and reconstruction of signals and images. In order to accelerate computation, the multiplicative and the additive half-quadratic reformulation of the original cost-function have been pioneered in Geman and Reynolds [IEEE Trans. Pattern Anal. Machine Intelligence, 14 (1992), pp. 367--383] and Geman and Yang IEEE Trans. Image Process., 4 (1995), pp. 932--946]. The alternate minimization of the resultant (augmented) cost-functions has a simple explicit form. The goal of this paper is to provide a systematic analysis of the convergence rate achieved by these methods. For the multiplicative and additive half-quadratic regularizations, we determine their upper bounds for their root-convergence factors. The bound for the multiplicative form is seen to be always smaller than the bound for the additive form. Experiments show that the number of iterations required for convergence for the multiplicative form is always less than that for the additive form. However, the computational cost of each iteration is much higher for the multiplicative form than for the additive form. The global assessment is that minimization using the additive form of half-quadratic regularization is faster than using the multiplicative form. When the additive form is applicable, it is hence recommended. Extensive experiments demonstrate that in our MATLAB implementation, both methods are substantially faster (in terms of computational times) than the standard MATLAB Optimization Toolbox routines used in our comparison study.

Original languageEnglish
Pages (from-to)937-966
Number of pages30
JournalSIAM Journal on Scientific Computing
Volume27
Issue number3
DOIs
Publication statusPublished - May 2005

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Convergence analysis
  • Half-quadratic regularization
  • Inverse problems
  • Maximum a posteriori estimation
  • Optimization
  • Preconditioning
  • Signal and image restoration
  • Variational methods

Fingerprint

Dive into the research topics of 'Analysis of Half-Quadratic Minimization Methods for Signal and Image Recovery'. Together they form a unique fingerprint.

Cite this