File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Convergence study on the symmetric version of admm with larger step sizes

TitleConvergence study on the symmetric version of admm with larger step sizes
Authors
KeywordsImage reconstruction
Convergence analysis
Alternating direction method of multipliers
Split Bregman
Large step size
Convex programming
Issue Date2016
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/siims.php
Citation
SIAM Journal on Imaging Sciences, 2016, v. 9, n. 3, p. 1467-1501 How to Cite?
Abstract© 2016 Society for Industrial and Applied Mathematics. The alternating direction method of multipliers (ADMM), also well known as a special split Bregman algorithm in imaging, is being popularly used in many areas including the image processing field. One useful modification is the symmetric version of the original ADMM, which updates the Lagrange multiplier twice at each iteration and thus the variables are treated in a symmetric manner. The symmetric version of ADMM, however, is not necessarily convergent. It was recently found that the convergence of symmetric ADMM can be suficiently ensured if both the step sizes for updating the Lagrange multiplier are shrunk conservatively. Despite the theoretical significance in ensuring convergence, however, smaller step sizes should be strongly avoided in practice. On the contrary, we actually have the desire of seeking larger step sizes whenever possible in order to accelerate the numerical performance. Another technique leading to numerical acceleration of ADMM is enlarging its step size by a constant originally proposed by Fortin and Glowinski. These two numerically favorable techniques are commonly but usually separately used in ADMM literature, and intuitively they seem to be incompatible in combination with the symmetric ADMM due to the conflict between the theoretical role in ensuring the convergence with smaller step sizes and the empirical necessity in accelerating numerical performance with larger step sizes. It is thus open whether the ADMM scheme in combination with these two techniques simultaneously is convergent. We answer this question affirmatively in this paper and rigorously show the convergence of the symmetric version of ADMM with step sizes that can be enlarged by Fortin and Glowinski's constant. We thus move forward to the counterintuitive understanding that shrinking both the step sizes is not necessary for the symmetric ADMM. We conduct the convergence analysis by specifying a step size domain that can ensure the convergence of symmetric ADMM; some known results in the ADMM literature turn out to be special cases of our discussion. Since the step sizes can be enlarged by constants that are problem-independent and the strategy is applicable to the general iterative scheme when the generic setting of the model is considered, our theoretical study provides an easily implementable strategy to accelerate the ADMM numerically which can be immediately applied to a variety of applications including some standard image processing tasks.
Persistent Identifierhttp://hdl.handle.net/10722/251179
ISSN
2020 Impact Factor: 2.867
2020 SCImago Journal Rankings: 0.944
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHe, Bing Sheng-
dc.contributor.authorMa, Feng-
dc.contributor.authorYuan, Xiao Ming-
dc.date.accessioned2018-02-01T01:54:49Z-
dc.date.available2018-02-01T01:54:49Z-
dc.date.issued2016-
dc.identifier.citationSIAM Journal on Imaging Sciences, 2016, v. 9, n. 3, p. 1467-1501-
dc.identifier.issn1936-4954-
dc.identifier.urihttp://hdl.handle.net/10722/251179-
dc.description.abstract© 2016 Society for Industrial and Applied Mathematics. The alternating direction method of multipliers (ADMM), also well known as a special split Bregman algorithm in imaging, is being popularly used in many areas including the image processing field. One useful modification is the symmetric version of the original ADMM, which updates the Lagrange multiplier twice at each iteration and thus the variables are treated in a symmetric manner. The symmetric version of ADMM, however, is not necessarily convergent. It was recently found that the convergence of symmetric ADMM can be suficiently ensured if both the step sizes for updating the Lagrange multiplier are shrunk conservatively. Despite the theoretical significance in ensuring convergence, however, smaller step sizes should be strongly avoided in practice. On the contrary, we actually have the desire of seeking larger step sizes whenever possible in order to accelerate the numerical performance. Another technique leading to numerical acceleration of ADMM is enlarging its step size by a constant originally proposed by Fortin and Glowinski. These two numerically favorable techniques are commonly but usually separately used in ADMM literature, and intuitively they seem to be incompatible in combination with the symmetric ADMM due to the conflict between the theoretical role in ensuring the convergence with smaller step sizes and the empirical necessity in accelerating numerical performance with larger step sizes. It is thus open whether the ADMM scheme in combination with these two techniques simultaneously is convergent. We answer this question affirmatively in this paper and rigorously show the convergence of the symmetric version of ADMM with step sizes that can be enlarged by Fortin and Glowinski's constant. We thus move forward to the counterintuitive understanding that shrinking both the step sizes is not necessary for the symmetric ADMM. We conduct the convergence analysis by specifying a step size domain that can ensure the convergence of symmetric ADMM; some known results in the ADMM literature turn out to be special cases of our discussion. Since the step sizes can be enlarged by constants that are problem-independent and the strategy is applicable to the general iterative scheme when the generic setting of the model is considered, our theoretical study provides an easily implementable strategy to accelerate the ADMM numerically which can be immediately applied to a variety of applications including some standard image processing tasks.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/siims.php-
dc.relation.ispartofSIAM Journal on Imaging Sciences-
dc.subjectImage reconstruction-
dc.subjectConvergence analysis-
dc.subjectAlternating direction method of multipliers-
dc.subjectSplit Bregman-
dc.subjectLarge step size-
dc.subjectConvex programming-
dc.titleConvergence study on the symmetric version of admm with larger step sizes-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1137/15M1044448-
dc.identifier.scopuseid_2-s2.0-84989347534-
dc.identifier.volume9-
dc.identifier.issue3-
dc.identifier.spage1467-
dc.identifier.epage1501-
dc.identifier.isiWOS:000385277200023-
dc.identifier.issnl1936-4954-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats