Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit

DOI10.1090/MCOM/2965zbMath1329.49050arXiv1301.0542OpenAlexW2918202932MaRDI QIDQ3450036

Laurent Demanet, Xiangxiong Zhang

Publication date: 2 November 2015

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We provide a simple analysis of the Douglas-Rachford splitting algorithm in the context of $ell^1$ minimization with linear constraints, and quantify the asymptotic linear convergence rate in terms of principal angles between relevant vector spaces. In the compressed sensing setting, we show how to bound this rate in terms of the restricted isometry constant. More general iterative schemes obtained by $ell^2$-regularization and over-relaxation including the dual split Bregman method are also treated, which answers the question how to choose the relaxation and soft-thresholding parameters to accelerate the asymptotic convergence rate. We make no attempt at characterizing the transient regime preceding the onset of linear convergence.

Full work available at URL: https://arxiv.org/abs/1301.0542

zbMATH Keywords

relaxation parametercompressed sensingbasis pursuitDouglas-Rachford splitting algorithm\(\ell^1\)-minimizationasymptotic linear convergence rate

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical methods involving duality (49M29) Numerical methods of relaxation type (49M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Error forgetting of Bregman iteration
• Global convergence of a non-convex Douglas-Rachford iteration
• Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• Analysis and Generalizations of the Linearized Bregman Method
• The Split Bregman Method for L1-Regularized Problems
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• On Sparse Representations in Arbitrary Redundant Bases
• Decoding by Linear Programming
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Atomic Decomposition by Basis Pursuit
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• Numerical Methods for Computing Angles Between Linear Subspaces
• Active Sets, Nonsmoothness, and Sensitivity
• A dual split Bregman method for fast $\ell ^1$ minimization
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Fast Discrete Curvelet Transforms

Related Items (20)

Local R-linear convergence of ADMM-based algorithm for \(\ell_1\)-norm minimization with linear and box constraints ⋮ Conic optimization via operator splitting and homogeneous self-dual embedding ⋮ Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces ⋮ Convergence rates with inexact non-expansive operators ⋮ Sensitivity Analysis for Mirror-Stratifiable Convex Functions ⋮ Local convergence properties of Douglas-Rachford and alternating direction method of multipliers ⋮ A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing ⋮ On the linear convergence of the circumcentered-reflection method ⋮ Tight global linear convergence rate bounds for Douglas-Rachford splitting ⋮ The block-wise circumcentered-reflection method ⋮ Convergence analysis of the generalized Douglas-Rachford splitting method under Hölder subregularity assumptions ⋮ Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness ⋮ On the optimal relaxation parameters of Krasnosel'ski–Mann iteration ⋮ Local linear convergence analysis of Primal–Dual splitting methods ⋮ Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator ⋮ A simple and efficient convex optimization based bound-preserving high order accurate limiter for Cahn-Hilliard-Navier-Stokes system ⋮ An optimization based limiter for enforcing positivity in a semi-implicit discontinuous Galerkin scheme for compressible Navier-Stokes equations ⋮ The Douglas--Rachford Algorithm for Two (Not Necessarily Intersecting) Affine Subspaces ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming

Uses Software

• PDCO

This page was built for publication: Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit