Eventual linear convergence of the Douglas Rachford iteration for basis\n pursuit

2013/01/03 by Laurent Demanet, Xiangxiong Zhang, Demanet, Laurent +1 · 4 citations
Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Gas Dynamics and Kinetic Theory #Information Theory (cs.IT) #Numerical Analysis (math.NA) #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1301.0542

openalex publication_date 2013/01/03 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28

Abstract

We provide a simple analysis of the Douglas-Rachford splitting algorithm in\nthe context of \ℓ¹ minimization with linear constraints, and quantify the\nasymptotic linear convergence rate in terms of principal angles between\nrelevant vector spaces. In the compressed sensing setting, we show how to bound\nthis rate in terms of the restricted isometry constant. More general iterative\nschemes obtained by \ℓ²-regularization and over-relaxation including the\ndual split Bregman method are also treated, which answers the question how to\nchoose the relaxation and soft-thresholding parameters to accelerate the\nasymptotic convergence rate. We make no attempt at characterizing the transient\nregime preceding the onset of linear convergence.\n

Cited by

• Extending Douglas-Rachford Splitting for Convex Optimization
• Efficient optimization-based invariant-domain-preserving limiters in solving gas dynamics equations
• Exact Total Variation Minimizers as Non-Oscillatory Limiters in High-Order Methods for Conservation Laws
• Basis pursuit by inconsistent alternating projections

Related

• Convergence rates of Forward--Douglas--Rachford splitting method
• A convergent relaxation of the Douglas-Rachford algorithm
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting\n and ADMM
• Accelerated Linearized Bregman Method
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle