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 metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02456435
Contributor : Yvain Queau <>
Submitted on : Monday, January 27, 2020 - 1:14:20 PM
Last modification on : Wednesday, September 23, 2020 - 4:27:45 AM

File

sparsdrrate.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02456435, version 1

Citation

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⟩

Share

Metrics

Record views

18

Files downloads

14