Volume 54, pp. 176-197, 2021.

Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization

Jongho Park


In this paper, we propose an overlapping additive Schwarz method for total variation minimization based on a dual formulation. The $O(1/n)$-energy convergence of the proposed method is proven, where $n$ is the number of iterations. In addition, we introduce an interesting convergence property of the proposed method called pseudo-linear convergence; the energy decreases as fast as for linearly convergent algorithms until it reaches a particular value. It is shown that this particular value depends on the overlapping width $\delta$, and the proposed method becomes as efficient as linearly convergent algorithms if $\delta$ is large. As the latest domain decomposition methods for total variation minimization are sublinearly convergent, the proposed method outperforms them in the sense of the energy decay. Numerical experiments which support our theoretical results are provided.

Full Text (PDF) [1.7 MB], BibTeX

Key words

domain decomposition method, additive Schwarz method, total variation minimization, Rudin–Osher–Fatemi model, convergence rate

AMS subject classifications

65N55, 65Y05, 65K15, 68U10

< Back