Linear Convergence of the ADMM/Douglas-Rachford Algorithms for Piecewise Linear-Quadratic Functions and Application to Statistical Imaging

Timo Aspelmeier, C. Charitha, D. Russell Luke

Published 2015-08-18Version 1

We consider the problem of minimizing the sum of a convex, piecewise linear- quadratic function and a convex piecewise linear-quadratic function composed with an injective linear mapping. We show that, for such problems, iterates of the alternating directions method of multipliers converge linearly to fixed points from which the solution to the original problem can be computed. Our proof strategy uses duality and strong metric subregularity of the Douglas-Rachford fixed point mapping. Our analysis does not require strong convexity and yields error bounds to the set of model solutions. We demonstrate an application of this result to exact penalization for signal deconvolution and denoising with multiresolution statistical constraints.