Geodesic
A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
Chambolle, Antonin1 ; Pock, Thomas2
1CMAP, Ecole Polytechnique, CNRS, 91128 Palaiseau, France
2Institute for Computer Graphics and Vision, Graz University of Technology, 8010 Graz, Austria and Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, 1220 Vienna, Austria
The SMAI Journal of computational mathematics, Tome 1 (2015), pp. 29-54
Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

We analyze alternating descent algorithms for minimizing the sum of a quadratic function and block separable non-smooth functions. In case the quadratic interactions between the blocks are pairwise, we show that the schemes can be accelerated, leading to improved convergence rates with respect to related accelerated parallel proximal descent. As an application we obtain very fast algorithms for computing the proximity operator of the 2D and 3D total variation.

Publié le :
DOI : 10.5802/smai-jcm.3
Classification : 65K10, 65B99, 49M27, 49M29, 90C25
Keywords: block coordinate descent, Dykstra’s algorithms, first order methods, acceleration, FISTA

Chambolle, Antonin  1   ; Pock, Thomas  2

1 CMAP, Ecole Polytechnique, CNRS, 91128 Palaiseau, France
2 Institute for Computer Graphics and Vision, Graz University of Technology, 8010 Graz, Austria and Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, 1220 Vienna, Austria 
@article{SMAI-JCM_2015__1__29_0,
     author = {Chambolle, Antonin and Pock, Thomas},
     title = {A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions},
     journal = {The SMAI Journal of computational mathematics},
     pages = {29--54},
     year = {2015},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {1},
     doi = {10.5802/smai-jcm.3},
     mrnumber = {3620369},
     zbl = {1416.65170},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.3/}
}
TY  - JOUR
AU  - Chambolle, Antonin
AU  - Pock, Thomas
TI  - A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
JO  - The SMAI Journal of computational mathematics
PY  - 2015
SP  - 29
EP  - 54
VL  - 1
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.3/
DO  - 10.5802/smai-jcm.3
LA  - en
ID  - SMAI-JCM_2015__1__29_0
ER  - 
%0 Journal Article
%A Chambolle, Antonin
%A Pock, Thomas
%T A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
%J The SMAI Journal of computational mathematics
%D 2015
%P 29-54
%V 1
%I Société de Mathématiques Appliquées et Industrielles
%U http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.3/
%R 10.5802/smai-jcm.3
%G en
%F SMAI-JCM_2015__1__29_0
Chambolle, Antonin; Pock, Thomas. A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions. The SMAI Journal of computational mathematics, Tome 1 (2015), pp. 29-54. doi: 10.5802/smai-jcm.3

Cité par Sources :