A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions.

Antonin Chambolle (1) , Thomas Pock (2)

1 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
2 ICG - Institute for Computer Graphics and Vision [Graz]

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.

Mots clés: block coordinate descent; accelerated algorithms; rates of convergence; total variation minimization; Dykstra's algorithms; first order methods; acceleration; FISTA

Domaines: Analyse numérique [math.NA]; Optimisation et contrôle [math.OC]; Calcul parallèle, distribué et partagé [cs.DC]

Antonin Chambolle, Thomas Pock. A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions.. SMAI Journal of Computational Mathematics, 2015, 1, pp.29 - 54. ⟨10.5802/smai-jcm.3⟩. ⟨hal-01099182v3⟩