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

DOI10.1553/ETNA_VOL54S176zbMATH Open1473.65342arXiv1911.06639OpenAlexW2988902853MaRDI QIDQ2033682FDOQ2033682

Authors: Jong Ho Park 

Publication date: 17 June 2021

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

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.

Full work available at URL: https://arxiv.org/abs/1911.06639

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

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

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)

Cites Work

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

Cited In (4)

• Additive Schwarz methods for convex optimization with backtracking
• Accelerated additive Schwarz methods for convex optimization with adaptive restart
• Additive Schwarz methods for convex optimization -- convergence theory and acceleration
• 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)