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...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
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 |