Subspace Correction and Domain Decomposition Methods for Total Variation Minimization

The minimization of the total variation is a well-established technique of preserving
edges and discontinuities. Therefore it has wide applicability in image processing,
where one is interested in recovering a corrupted image while preserving edges in
the image. In the last decades, in the literature, there have been introduced many
different approaches and algorithms for minimizing the total variation. These standard techniques are iterative-sequentially formulated and therefore not able to solve
large scale simulations in acceptable computational time. For such large problems
we need to address methods that allow us to reduce the problem to a finite sequence
of subproblems of a more manageable size, perhaps computed by one of the standard
techniques. With this aim, we introduce subspace correction and domain decomposition methods for total variation minimization. Such methods split the space of
the initial problem into several smaller subspaces. By restricting the function to
be minimized to the subspaces, a sequence of local problems, which may be solved
easier and faster than the original problem, is constituted. Then the solution of the
initial problem is obtained via the solutions of the local subproblems by “gluing”
them together. In the case of domain decomposition for total variation minimization
the crucial difficulty is the correct treatment of the interfaces of the domain decomposition patches, with the preservation of crossing discontinuities and the correct
matching where the solution is continuous instead. Due to the fact that the total
variation is non-smooth and non-additive, one encounters additional difficulties in
showing convergence of more general subspace correction strategies to global minimizers. We show a classical counterexample from the literature, which emphasizes
that for non-smooth and non-additive problems such alternating techniques are far
from being obviously converging to an expected minimizer.
Moreover we discuss a subspace correction method for total variation minimization based on an orthogonal wavelet decomposition. For this algorithm we are able to
construct another counterexample, which confirms that in general we cannot expect
convergence of such splitting algorithms to a minimizer of the original problem.
Nevertheless, we are able to propose an implementation of overlapping and nonoverlapping domain decomposition algorithms for total variation minimization with
the guarantee of convergence to a minimizer of the original functional and the monotonic decay of the energy. Let us stress that these are the first successful attempts
of addressing domain decomposition strategies for the non-linear, non-additive, and
non-smooth problem of total variation minimization with a rigorous convergence
analysis. We provide several numerical experiments, showing the successful application of the algorithm for the restoration of 1D signals and 2D images.