A General Decomposition Method for a Convex Problem Related to Total Variation Minimization

Stephan Hilb; Andreas Langer

doi:10.5802/smai-jcm.140

Stephan Hilb ¹; Andreas Langer ²

¹Stuttgart, Germany
²Department for Mathematical Sciences, Lund University, Sweden

The SMAI Journal of computational mathematics, Volume 11 (2025), pp. 693-726

Abstract

We consider sequential and parallel decomposition methods for a dual problem of a general total variation minimization problem with applications in several image processing tasks, like image inpainting, estimation of optical flow and reconstruction of missing wavelet coefficients. The convergence of these methods to a solution of the global problem is analysed in a Hilbert space setting and a convergence rate is provided. Thereby, these convergence result hold not only for exact local minimization but also if the subproblems are just solved approximately. As a concrete example of an approximate local solution process a surrogate technique is presented and analysed. Further, the obtained convergence rate is compared with related results in the literature and shown to be in agreement with or even improve upon them. Numerical experiments are presented to support the theoretical findings and to show the performance of the proposed decomposition algorithms in image inpainting, optical flow estimation and wavelet inpainting tasks.

Published online: 2026-03-02

DOI: 10.5802/smai-jcm.140

Classification: 68U10, 94A08, 49M27, 65K10, 90C06
Keywords: domain decomposition, total variation minimization, convex optimization, image restoration, convergence analysis, subspace correction

Author's affiliations:

Stephan Hilb ¹ ; Andreas Langer ²

¹ Stuttgart, Germany
² Department for Mathematical Sciences, Lund University, Sweden

@article{SMAI-JCM_2025__11__693_0,
     author = {Stephan Hilb and Andreas Langer},
     title = {A {General} {Decomposition} {Method} for a {Convex} {Problem} {Related} to {Total} {Variation} {Minimization}},
     journal = {The SMAI Journal of computational mathematics},
     pages = {693--726},
     year = {2025},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {11},
     doi = {10.5802/smai-jcm.140},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.140/}
}

TY  - JOUR
AU  - Stephan Hilb
AU  - Andreas Langer
TI  - A General Decomposition Method for a Convex Problem Related to Total Variation Minimization
JO  - The SMAI Journal of computational mathematics
PY  - 2025
SP  - 693
EP  - 726
VL  - 11
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.140/
DO  - 10.5802/smai-jcm.140
LA  - en
ID  - SMAI-JCM_2025__11__693_0
ER  -

%0 Journal Article
%A Stephan Hilb
%A Andreas Langer
%T A General Decomposition Method for a Convex Problem Related to Total Variation Minimization
%J The SMAI Journal of computational mathematics
%D 2025
%P 693-726
%V 11
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.140/
%R 10.5802/smai-jcm.140
%G en
%F SMAI-JCM_2025__11__693_0

Stephan Hilb; Andreas Langer. A General Decomposition Method for a Convex Problem Related to Total Variation Minimization. The SMAI Journal of computational mathematics, Volume 11 (2025), pp. 693-726. doi: 10.5802/smai-jcm.140

References
Cited by

[1] Luigi Ambrosio; Nicola Fusco; Diego Pallara Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs, Clarendon Press, 2000, xviii+434 pages | MR | Zbl | DOI

[2] Hedy Attouch; Giuseppe Buttazzo; Gérard Michaille Variational Analysis in Sobolev and BV Spaces, MOS-SIAM Series on Optimization, Mathematical Optimization Society; Society for Industrial and Applied Mathematics, 2014, xii+793 pages | DOI | MR | Zbl

[3] Gilles Aubert; Pierre Kornprobst Mathematical Problems in Image Processing, Applied Mathematical Sciences, 147, Springer, 2006, xxxii+377 pages | MR | Zbl

[4] Lori Badea Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals, SIAM J. Numer. Anal., Volume 44 (2006) no. 2, pp. 449-477 | DOI | Zbl | MR

[5] Simon Baker; Daniel Scharstein; James P. Lewis; Stefan Roth; Michael J. Black; Richard Szeliski A Database and Evaluation Methodology for Optical Flow, Int. J. Comput. Vis., Volume 92 (2011) no. 1, pp. 1-31 | DOI

[6] Amir Beck; Marc Teboulle A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., Volume 2 (2009) no. 1, pp. 183-202 | DOI | Zbl | MR

[7] Jakub W. Both On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces, Optim. Lett., Volume 16 (2022) no. 2, pp. 729-743 | DOI | Zbl | MR

[8] Antonin Chambolle An Algorithm for Total Variation Minimization and Applications, J. Math. Imaging Vis., Volume 20 (2004) no. 1-2, pp. 89-97 | DOI | MR | Zbl

[9] Antonin Chambolle; Thomas Pock A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, SMAI J. Comput. Math., Volume 1 (2015), pp. 29-54 | MR | Numdam | DOI | Zbl

[10] Huibin Chang; Xue-Cheng Tai; Li-Lian Wang; Danping Yang Convergence Rate of Overlapping Domain Decomposition Methods for the Rudin–Osher–Fatemi Model Based on a Dual Formulation, SIAM J. Imaging Sci., Volume 8 (2015) no. 1, pp. 564-591 | DOI | Zbl | MR

[11] Patrick L. Combettes; Valérie R. Wajs Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., Volume 4 (2005) no. 4, pp. 1168-1200 | DOI | MR | Zbl

[12] Ingrid Daubechies; Michel Defrise; Christine De Mol An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., Volume 57 (2004) no. 11, pp. 1413-1457 | DOI | MR | Zbl

[13] Ingrid Daubechies; Gerd Teschke; Luminita Vese Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging, Volume 1 (2007) no. 1, pp. 29-46 | DOI | MR | Zbl

[14] Victorita Dolean; Pierre Jolivet; Frédéric Nataf An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation, Society for Industrial and Applied Mathematics, 2015 | DOI | Zbl | MR

[15] Joseph C. Dunn Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals, SIAM J. Control Optim., Volume 17 (1979) no. 2, pp. 187-211 | DOI | Zbl | MR

[16] Ivar Ekeland; Roger Témam Convex Analysis and Variational Problems, Classics in Applied Mathematics, 28, Society for Industrial and Applied Mathematics, 1999, xiv+402 pages (Translated from the French) | DOI | MR | Zbl

[17] Massimo Fornasier; Yunho Kim; Andreas Langer; Carola-Bibiane Schönlieb Wavelet Decomposition Method for $L_{2}$ /TV-Image Deblurring, SIAM J. Imaging Sci., Volume 5 (2012) no. 3, pp. 857-885 | DOI | Zbl | MR

[18] Massimo Fornasier; Andreas Langer; Carola-Bibiane Schönlieb A convergent overlapping domain decomposition method for total variation minimization, Numer. Math., Volume 116 (2010) no. 4, pp. 645-685 | DOI | Zbl | MR

[19] Massimo Fornasier; Carola-Bibiane Schönlieb Subspace correction methods for total variation and $l_{1}$ -minimization, SIAM J. Numer. Anal., Volume 47 (2009) no. 5, pp. 3397-3428 | DOI | MR | Zbl

[20] Stephan Hilb DualTVDD: Dual total variation decomposition algorithm and related tools, 2021 (https://gitlab.mathematik.uni-stuttgart.de/stephan.hilb/DualTVDD.jl)

[21] Stephan Hilb; Andreas Langer; Martin Alkämper A Primal-Dual Finite Element Method for Scalar and Vectorial Total Variation Minimization, J. Sci. Comput., Volume 96 (2023) no. 1, 24, 33 pages | Zbl | MR

[22] Michael Hintermüller; Karl Kunisch Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math., Volume 64 (2004) no. 4, pp. 1311-1333 | Zbl | MR

[23] Michael Hintermüller; Andreas Langer Subspace correction methods for a class of nonsmooth and nonadditive convex variational problems with mixed $L^{1} / L^{2}$ data-fidelity in image processing, SIAM J. Imaging Sci., Volume 6 (2013) no. 4, pp. 2134-2173 | DOI | MR | Zbl

[24] Michael Hintermüller; Andreas Langer Surrogate Functional Based Subspace Correction Methods for Image Processing, Domain Decomposition Methods in Science and Engineering XXI, Springer, 2014, pp. 829-837 | DOI | Zbl

[25] Michael Hintermüller; Andreas Langer Non-overlapping domain decomposition methods for dual total variation based image denoising, J. Sci. Comput., Volume 62 (2015) no. 2, pp. 456-481 | Zbl | MR | DOI

[26] Kazufumi Ito; Karl Kunisch Lagrange Multiplier Approach to Variational Problems and Applications, Advances in Design and Control, Society for Industrial and Applied Mathematics, 2008 | MR | DOI | Zbl

[27] Mikael Kurula; Hans Zwart The duality between the gradient and divergence operators on bounded Lipschitz domains, 2012 (University of Twente)

[28] Andreas Langer Domain Decomposition for Non-smooth (in Particular TV) Minimization, Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging: Mathematical Imaging and Vision, Springer, 2021, pp. 1-47 | DOI | Zbl

[29] Andreas Langer; Fernando Gaspoz Overlapping Domain Decomposition Methods for Total Variation Denoising, SIAM J. Numer. Anal., Volume 57 (2019) no. 3, pp. 1411-1444 | DOI | Zbl | MR

[30] Andreas Langer; Stanley Osher; Carola-Bibiane Schönlieb Bregmanized domain decomposition for image restoration, J. Sci. Comput., Volume 54 (2013) no. 2-3, pp. 549-576 | DOI | MR | Zbl

[31] Chang-Ock Lee; Changmin Nam Primal Domain Decomposition Methods for the Total Variation Minimization, Based on Dual Decomposition, SIAM J. Sci. Comput., Volume 39 (2017) no. 2, p. B403-B423 | Zbl | MR

[32] Chang-Ock Lee; Changmin Nam; Jongho Park Domain Decomposition Methods Using Dual Conversion for the Total Variation Minimization with $L^{1}$ Fidelity Term, J. Sci. Comput., Volume 78 (2019) no. 2, pp. 951-970 | MR | Zbl

[33] Chang-Ock Lee; Eun-Hee Park; Jongho Park A finite element approach for the dual Rudin–Osher–Fatemi model and its nonoverlapping domain decomposition methods, SIAM J. Sci. Comput., Volume 41 (2019) no. 2, p. B205-B228 | Zbl | MR

[34] Chang-Ock Lee; Jongho Park Fast Nonoverlapping Block Jacobi Method for the Dual Rudin–Osher–Fatemi Model, SIAM J. Imaging Sci., Volume 12 (2019) no. 4, pp. 2009-2034 | MR | Zbl

[35] Chang-Ock Lee; Jongho Park A finite element nonoverlapping domain decomposition method with Lagrange multipliers for the dual total variation minimizations, J. Sci. Comput., Volume 81 (2019) no. 3, pp. 2331-2355 | Zbl | MR

[36] Chang-Ock Lee; Jongho Park Recent advances in domain decomposition methods for total variation minimization, J. Korean Soc. Ind. Appl. Math., Volume 24 (2020) no. 2, pp. 161-197 | Zbl | MR

[37] Xue Li; Zhenwei Zhang; Huibin Chang; Yuping Duan Accelerated Non-Overlapping Domain Decomposition Method for Total Variation Minimization, Numer. Math., Theory Methods Appl., Volume 14 (2021) no. 4, pp. 1017-1041 | Zbl | MR

[38] Julien Mairal Optimization with first-order surrogate functions, Proceedings of the 30th International Conference on Machine Learning (Proceedings of Machine Learning Research), Volume 28, PMLR (2013), pp. 783-791

[39] Reinhard Nabben Comparisons between multiplicative and additive Schwarz iterations in domain decomposition methods, Numer. Math., Volume 95 (2003), pp. 145-162 | DOI | MR | Zbl

[40] Yurii Nesterov A method of solving a convex programming problem with convergence rate $𝒪 (1 / k^{2})$ , Sov. Math., Dokl., Volume 27 (1983) no. 2, pp. 372-376

[41] Jongho Park Additive Schwarz methods for convex optimization as gradient methods, SIAM J. Numer. Anal., Volume 58 (2020) no. 3, pp. 1495-1530 | DOI | MR

[42] Jongho Park An overlapping domain decomposition framework without dual formulation for variational imaging problems, Adv. Comput. Math., Volume 46 (2020) no. 4, 57, 29 pages | MR

[43] Jongho Park Accelerated additive Schwarz methods for convex optimization with adaptive restart, J. Sci. Comput., Volume 89 (2021) no. 3, 58, 20 pages | MR

[44] Jongho Park Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization, Electron. Trans. Numer. Anal., Volume 54 (2021), pp. 176-197 | DOI | MR

[45] Alfio Quarteroni; Alberto Valli Domain Decomposition Methods for Partial Differential Equations, Clarendon Press, 1999 | MR

[46] Xue-Cheng Tai Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math., Volume 93 (2003) no. 4, pp. 755-786 | MR

[47] Andrea Toselli; Olof B. Widlund Domain Decomposition Methods: Algorithms and Theory, Springer Series in Computational Mathematics, 34, Springer, 2005 | DOI | MR

[48] Jinchao Xu; Ludmil Zikatanov The method of alternating projections and the method of subspace corrections in Hilbert space, J. Am. Math. Soc., Volume 15 (2002) no. 3, pp. 573-597 | MR

[49] Zhenwei Zhang; Huibin Chang; Yuping Duan Fast Non-overlapping Domain Decomposition Methods for Continuous Multi-phase Labeling Problem, J. Sci. Comput., Volume 97 (2023) no. 3, 67, 29 pages | MR

Cited by Sources: