Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Yvain Queau Connect in order to contact the contributor
Submitted on : Monday, January 27, 2020 - 1:14:20 PM
Last modification on : Saturday, June 25, 2022 - 9:55:35 AM


Files produced by the author(s)


  • HAL Id : hal-02456435, version 1


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⟩



Record views


Files downloads