![]() |
ETNA - Electronic Transactions on Numerical Analysis
|
![]() |
Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A-1011 Wien, Dr. Ignaz Seipel-Platz 2
Tel. +43-1-515 81/DW 3420, Fax +43-1-515 81/DW 3400 https://verlag.oeaw.ac.at, e-mail: verlag@oeaw.ac.at |
|
||||||||||||||||||||
|
DATUM, UNTERSCHRIFT / DATE, SIGNATURE
BANK AUSTRIA CREDITANSTALT, WIEN (IBAN AT04 1100 0006 2280 0100, BIC BKAUATWW), DEUTSCHE BANK MÜNCHEN (IBAN DE16 7007 0024 0238 8270 00, BIC DEUTDEDBMUC)
|

ETNA - Electronic Transactions on Numerical Analysis, pp. 15-49, 2019/03/01
We study and develop (stochastic) primal-dual block-coordinate descentmethods for convex problems based on the method due to Chambolle and Pock.Our methods have known convergence rates for the iterates and the ergodicgap of$O(1/N^2)$ if each block is strongly convex, $O(1/N)$ if no convexity ispresent, and more generally a mixed rate $O(1/N^2)+O(1/N)$for strongly convex blocks if only some blocks are strongly convex.Additional novelties of our methods include blockwise-adapted step lengthsand acceleration as well as the ability to update both the primal and dualvariables randomly in blocks under a very light compatibility condition. Inother words, these variants of our methods are doubly-stochastic.We test the proposed methods on various image processing problems, wherewe employ pixelwise-adapted acceleration.
Keywords: PDHGM, Chambolle–Pock method, stochastic, doubly-stochastic, blockwise, primal-dual