A comparison of multilevel methods for total variation regularization.

*(English)*Zbl 0888.65135Summary: We consider numerical methods for solving problems involving total variation (TV) regularization for semidefinite quadratic minimization problems \(\min_u|{\mathcal K}u- z|^2_2\) arising from ill-posed 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 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 porous media flow models.

The Euler equation for the regularized objective functional is a quasilinear elliptic equation of the form \([{\mathcal K}^*{\mathcal K}+ A(u)]u= -{\mathcal K}^*z\). Here, \(A(u)\) is a standard selfadjoint second-order elliptic operator in which the coefficient \(\kappa\) depends on \(u\), by \([\kappa(u)](x)= 1/|\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.

The Euler equation for the regularized objective functional is a quasilinear elliptic equation of the form \([{\mathcal K}^*{\mathcal K}+ A(u)]u= -{\mathcal K}^*z\). Here, \(A(u)\) is a standard selfadjoint second-order elliptic operator in which the coefficient \(\kappa\) depends on \(u\), by \([\kappa(u)](x)= 1/|\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.

##### MSC:

65Z05 | Applications to the sciences |

65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |

35R30 | Inverse problems for PDEs |

35J65 | Nonlinear boundary value problems for linear elliptic equations |