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

[摘要] 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.

[学科分类] 数学（综合）

[关键词] domain decomposition method;additive Schwarz method;total variation minimization;Rudin–Osher–Fatemi model;convergence rate