Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation

This paper is concerned with overlapping domain decomposition methods (DDMs), based on successive subspace correction (SSC) and parallel subspace correction (PSC), for the Rudin--Osher--Fatemi (ROF) model in image restoration. In contrast to recent attempts, we work with a dual formulation of the RO...

Full description

Saved in:
Bibliographic Details
Main Authors: Chang, Huibin, Tai, Xue-Cheng, Wang, Li-Lian, Yang, Danping
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2015
Subjects:
Online Access:https://hdl.handle.net/10356/107393
http://hdl.handle.net/10220/25525
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-107393
record_format dspace
spelling sg-ntu-dr.10356-1073932023-02-28T19:46:58Z Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation Chang, Huibin Tai, Xue-Cheng Wang, Li-Lian Yang, Danping School of Physical and Mathematical Sciences DRNTU::Science::Biological sciences This paper is concerned with overlapping domain decomposition methods (DDMs), based on successive subspace correction (SSC) and parallel subspace correction (PSC), for the Rudin--Osher--Fatemi (ROF) model in image restoration. In contrast to recent attempts, we work with a dual formulation of the ROF model, where one significant difficulty resides in the decomposition of the global constraint of the dual variable. We introduce a stable “unity decomposition” using a set of “partition of unity functions,” which naturally leads to overlapping DDMs based on the dual formulation. The main objective of this paper is to rigorously analyze the convergence of the SSC and PSC algorithms and derive the rate of convergence $O(n^{-1/2})$, where $n$ is the number of iterations. Moreover, we characterize the explicit dependence of the convergence rate on the subdomain overlapping size and other important parameters. To the best of our knowledge, such a convergence rate has not yet been claimed for domain decomposition related algorithms for the ROF model. Published version 2015-05-14T02:42:02Z 2019-12-06T22:29:59Z 2015-05-14T02:42:02Z 2019-12-06T22:29:59Z 2015 2015 Journal Article Chang, H., Tai, X.-C., Wang, L. L., & Yang, D. (2015). Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation. SIAM journal on imaging sciences, 8(1), 564-591. 1936-4954 https://hdl.handle.net/10356/107393 http://hdl.handle.net/10220/25525 10.1137/140965016 en SIAM journal on imaging sciences © 2015 Society for Industrial and Applied Mathematics. This paper was published in SIAM Journal on Imaging Sciences and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official DOI: [http://dx.doi.org/10.1137/140965016]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. 28 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Biological sciences
spellingShingle DRNTU::Science::Biological sciences
Chang, Huibin
Tai, Xue-Cheng
Wang, Li-Lian
Yang, Danping
Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
description This paper is concerned with overlapping domain decomposition methods (DDMs), based on successive subspace correction (SSC) and parallel subspace correction (PSC), for the Rudin--Osher--Fatemi (ROF) model in image restoration. In contrast to recent attempts, we work with a dual formulation of the ROF model, where one significant difficulty resides in the decomposition of the global constraint of the dual variable. We introduce a stable “unity decomposition” using a set of “partition of unity functions,” which naturally leads to overlapping DDMs based on the dual formulation. The main objective of this paper is to rigorously analyze the convergence of the SSC and PSC algorithms and derive the rate of convergence $O(n^{-1/2})$, where $n$ is the number of iterations. Moreover, we characterize the explicit dependence of the convergence rate on the subdomain overlapping size and other important parameters. To the best of our knowledge, such a convergence rate has not yet been claimed for domain decomposition related algorithms for the ROF model.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Chang, Huibin
Tai, Xue-Cheng
Wang, Li-Lian
Yang, Danping
format Article
author Chang, Huibin
Tai, Xue-Cheng
Wang, Li-Lian
Yang, Danping
author_sort Chang, Huibin
title Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
title_short Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
title_full Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
title_fullStr Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
title_full_unstemmed Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation
title_sort convergence rate of overlapping domain decomposition methods for the rudin-osher-fatemi model based on a dual formulation
publishDate 2015
url https://hdl.handle.net/10356/107393
http://hdl.handle.net/10220/25525
_version_ 1759858294778757120