Convergence Analysis of Block-Coordinate Primal-Dual Algorithms with Arbitrary Random Sampling

A. Repetti, E. Chouzenoux et J.-C. Pesquet.

ISMP 2015,
Pittsburgh, PA, 12-17 Juillet 2017.

In many application areas, one must solve minimization problems involving the sum of proper lower-semicontinuous convex functions composed with linear operators. Such problems can be efficiently solved using primal-dual proximal algorithms. When the number of variables is very large, it can be interesting to adopt a block-coordinate strategy in order to limit the occupied memory. In this work, we propose two subclasses of block-coordinate primal-dual algorithms based on the forward-backward iterative scheme. At each iteration, only a subpart of the variables, selected with an arbitrary random rule, is updated. The almost sure convergence of the iterates generated by the algorithms to a solution of the considered problem is proved.




Biomedical and Astronomical Signal Processing group
Institute of Sensors, Signals and Systems
Heriot-Watt University
Edinburgh EH14 4AS
Scotland UK

mail: A.Repetti@hw.ac.uk