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

DOI10.1553/ETNA_VOL54S176MaRDI QIDQ2033682zbMATH OpenOpenAlexFDO

Authors Jong Ho Park

Publication date 17 June 2021

Published in ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.06639, http://etna.mcs.kent.edu/volumes/2021-2030/vol54/abstract.php?vol=54&pages=176-197

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

convergence ratedomain decomposition methodadditive Schwarz methodtotal variation minimizationRudin-Osher-Fatemi model

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12)

Abstract: 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 called pseudo-linear convergence of the proposed method; the energy of the proposed method decreases as fast as linearly convergent algorithms until it reaches a particular value. It is shown that such the 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.

Recommendations

• A convergent overlapping domain decomposition method for total variation minimization
• Overlapping domain decomposition methods for total variation denoising
• Dual-primal domain decomposition methods for the total variation minimization
• Additive Schwarz methods for convex optimization as gradient methods
• Primal domain decomposition methods for the total variation minimization, based on dual decomposition

Cites work

• scientific article; zbMATH DE number 3564235 (Why is no real title available?)
• scientific article; zbMATH DE number 2113718 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• scientific article; zbMATH DE number 5180707 (Why is no real title available?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A convergent overlapping domain decomposition method for total variation minimization
• A finite element approach for the dual Rudin-Osher-Fatemi model and its nonoverlapping domain decomposition methods
• A finite element nonoverlapping domain decomposition method with Lagrange multipliers for the dual total variation minimizations
• A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
• An algorithm for total variation minimization and applications
• An introduction to continuous optimization for imaging
• An overlapping Schwarz algorithm for Raviart-Thomas vector fields with discontinuous coefficients
• Cahn-Hilliard inpainting and a generalization for grayvalue images
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Convergence Rate Analysis of a Multiplicative Schwarz Method for Variational Inequalities
• Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
• Discrete total variation with finite elements and applications to imaging
• Fast nonoverlapping block Jacobi method for the dual Rudin-Osher-Fatemi model
• Global and uniform convergence of subspace correction methods for some convex optimization problems
• Image Decomposition and Restoration Using Total Variation Minimization and theH¹
• Non-overlapping domain decomposition methods for dual total variation based image denoising
• Nonlinear total variation based noise removal algorithms
• On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
• One- and two-level Schwarz methods for variational inequalities of the second kind and their application to frictional contact
• Overlapping domain decomposition methods for total variation denoising
• Primal domain decomposition methods for the total variation minimization, based on dual decomposition
• Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities
• Subspace correction methods for total variation and _1-minimization
• Total variation minimization with an \(H^{-1}\) constraint

Cited in

(6)

• Additive Schwarz methods for convex optimization with backtracking
• Accelerated additive Schwarz methods for convex optimization with adaptive restart
• A general decomposition method for a convex problem related to total variation minimization
• Additive Schwarz methods for convex optimization -- convergence theory and acceleration
• Randomized subspace correction methods for convex optimization
• Fast gradient methods for uniformly convex and weakly smooth problems

This page was built for publication: Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033682)