A Comparison of Multilevel Methods for Total Variation Regularization

Panayot Vassilevksi and Gordon Wade

Department of Mathematics and Statistics
Bowling Green State University
Bowling Green, OH, 43403-0221


We consider numerical methods for solving problems involving total variation (TV) regularization for semidefinite quadratic minimization problems for image recontruction. The objective functional (before regularization) is the norm squared of (Lu-z), where u is the reconstructed image, L is a compact linear operator, and z is data containing inexact or partial information about the image. TV regularization entails adding to the objective functional a term which penalizes the total variation of u; this term formally appears as (a scalar times) the L1 norm of the gradient of u. The Euler equation for the regularized objective functional is a quasilinear elliptic equation of the form

   [ L^*L + A(u) ] u = -L^*z
in two space dimensions. Here, A(u) is a standard self-adjoint second order elliptic operator in which the coefficient a depends on u, by
   [a(u)](x) = c/sqrt(|grad u(x)|^2 + b^2)
where b and c are small constants. A common and effective strategy for solving the Euler equation is the fixed point method.

Total variation regularization has enjoyed significant success in image denoising and deblurring, laser interferometry, electrical tomography, and estimation of permeabilities in porus medua flow models. Its main advantage is that it improves the conditioning of the optimization problem while not penalizing discontinuities in the reconstructed image. The main difficulty in its use lies in the fact that the Euler equation is nonlinear with rapidly varying coefficients and can have a rather large number (e.g., 640-squared) of degrees of freedom.

In this paper we present results from numerical experiments in which we use a fixed point approach to solving the the Euler equations, using various multilevel preconditioners. Specifically, we shall explore the performance of the "Hierarchical Basis" method, the "wavelet-modified Hierarchical Basis" method, and a conventional multigrid method.

Additional information will become available here via WWW.