Volume 6, pp. 255-270, 1997.

A comparison of multilevel methods for total variation regularization

P. S. Vassilevski and J. G. Wade

Abstract

We consider numerical methods for solving problems involving total variation (TV) regularization for semidefinite quadratic minimization problems $\underset{u}{min}\Vert \mathcal{K}u-z{\Vert }_2^2$ arising from illposed inverse problems. Here $\mathcal{K}$ is a compact linear operator, and $z$ is data containing inexact or partial information about the “true” $u$. TV regularization entails adding to the objective function a penalty term which is a scalar multiple of the total variation of $u$; this term formally appears as (a scalar times) the $L^1$ norm of the gradient of $u$. The advantage of this regularization is that it improves the conditioning of the optimization problem while {\em not penalizing discontinuities} in the reconstructed image. This approach has enjoyed significant success in image denoising and deblurring, laser interferometry, electrical tomography, and estimation of permeabilities in porus media flow models. The Euler equation for the regularized objective functional is a quasilinear elliptic equation of the form $[{\mathcal{K}}^{\ast }\mathcal{K}+A(u)]u=-{\mathcal{K}}^{\ast }z.$ Here, $A(u)$ is a standard self-adjoint second order elliptic operator in which the coefficient $\kappa$ depends on $u$, by $[\kappa (u)](x)=1/|\mathrm{\nabla }u(x)|$. Following the literature, we approach the Euler equation by means of fixed point iterations, resulting in a sequence of linear subproblems. In this paper we present results from numerical experiments in which we use the preconditioned conjugate gradient method on the linear subproblems, with various multilevel iterative methods used as preconditioners.

Full Text (PDF) [1001 KB], BibTeX

Key words

total variation, regularization, multilevel methods, inverse problems.

AMS subject classifications

65N55, 35R30, 65F10.