Local Linear Convergence of Douglas-Rachford/ADMM for Low Complexity Regularization

Jingwei Liang (1) , Jalal M. Fadili (1) , Gabriel Peyré (2) , Russell Luke (3)

1 Equipe Image - Laboratoire GREYC - UMR6072
2 CEREMADE - CEntre de REcherches en MAthématiques de la DEcision
3 NAM - Mathematics Department [Gottingen]

The Douglas-Rachford (DR) and ADMM algorithms have become popular to solve sparse recovery problems and beyond. The goal of this work is to understand the local convergence behaviour of DR/ADMM which have been observed in practice to exhibit local linear convergence. We show that when the involved functions (resp. their Legendre-Fenchel conjugates) are partly smooth, the DR (resp. ADMM) method identifies their associated active manifolds in finite time. Moreover, when these functions are partly polyhedral, we prove that DR (resp. ADMM) is locally linearly convergent with a rate in terms of the cosine of the Friedrichs angle between the tangent spaces of the two active manifolds. This is illustrated by several concrete examples and supported by numerical experiments.

Domains: Computer Science [cs]; Image Processing [eess.IV]

Jingwei Liang, Jalal M. Fadili, Gabriel Peyré, Russell Luke. Local Linear Convergence of Douglas-Rachford/ADMM for Low Complexity Regularization. SPARS, 2015, Cambridge, United Kingdom. ⟨hal-02456435⟩