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)

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)

Related Items (18)

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 ⋮ 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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

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