Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging

DOI10.1137/15M103580XzbMath1347.49046arXiv1508.04468MaRDI QIDQ3188209

D. Russell Luke, C. Charitha, Timo Aspelmeier

Publication date: 17 August 2016

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

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

zbMATH Keywords

fixed point theoryimage processinginverse problemslinear convergencemetric regularityexact penalizationaugmented LagrangianDouglas-Rachford algorithmalternating directions method of multipliersstatistical multiscale analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical optimization and variational techniques (65K10) Nonsmooth analysis (49J52) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Inverse problems in linear algebra (15A29) Numerical methods of relaxation type (49M20) Inverse problems in optimal control (49N45)

Related Items

Local R-linear convergence of ADMM-based algorithm for \(\ell_1\)-norm minimization with linear and box constraints ⋮ On applications of the calmness moduli for multifunctions to error bounds ⋮ Convergence of proximal splitting algorithms in \(\operatorname{CAT}(\kappa)\) spaces and beyond ⋮ Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers ⋮ Isotonicity of the proximity operator and stochastic optimization problems in Hilbert quasi-lattices endowed with Lorentz cones ⋮ Unnamed Item ⋮ Weak Sharp Minima for Convex Infinite Optimization Problems in Normed Linear Spaces ⋮ A globally linearly convergent method for pointwise quadratically supportable convex-concave saddle point problems ⋮ A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance ⋮ Proximal Activation of Smooth Functions in Splitting Algorithms for Convex Image Recovery ⋮ A continuous dynamical splitting method for solving ‘strongly+weakly’ convex programming problems ⋮ Convergence rate of the relaxed CQ algorithm under Hölderian type error bound property ⋮ Isotonicity of the proximity operator and mixed variational inequalities in Hilbert spaces ⋮ Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator ⋮ A convergent relaxation of the Douglas-Rachford algorithm ⋮ Over relaxed hybrid proximal extragradient algorithm and its application to several operator splitting methods ⋮ Necessary conditions for linear convergence of iterated expansive, set-valued mappings ⋮ Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings ⋮ Preconditioned proximal point methods and notions of partial subregularity ⋮ \( \alpha \)-firmly nonexpansive operators on metric spaces ⋮ Metric regularity relative to a cone ⋮ An adaptive alternating direction method of multipliers ⋮ Split-Douglas--Rachford Algorithm for Composite Monotone Inclusions and Split-ADMM ⋮ A primal-dual flow for affine constrained convex optimization ⋮ Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Nonsmooth optimization via quasi-Newton methods
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Local linear convergence of approximate projections onto regularized sets
• Convex analysis and nonlinear optimization. Theory and examples.
• Local linear convergence for alternating and averaged nonconvex projections
• Optimization methods and stability of inclusions in Banach spaces
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• Statistical multiresolution Dantzig estimation in imaging: fundamental concepts and algorithmic framework
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• On the local convergence of the Douglas-Rachford algorithm
• Statistical multiresolution estimation for variational imaging: with an application in Poisson-biophotonics
• Linear convergence of the Douglas–Rachford method for two closed sets
• The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than $1/k^2$
• Calculus Without Derivatives
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• On Weak Convergence of the Douglas–Rachford Method
• Weak Sharp Minima in Mathematical Programming
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness
• Implicit Functions and Solution Mappings
• Exact Regularization of Convex Programs
• Optimization and nonsmooth analysis
• Exact penalty functions in nonlinear programming
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• An Exact Penalization Viewpoint of Constrained Optimization
• Monotone Operators and the Proximal Point Algorithm
• Numerical Optimization
• Variational Analysis
• Trust Region Methods
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Fast Alternating Direction Optimization Methods
• Sufficiency of Exact Penalty Minimization
• The Cyclic Douglas-Rachford Method for Inconsistent Feasibility Problems
• Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Proximité et dualité dans un espace hilbertien
• Convex analysis and monotone operator theory in Hilbert spaces
• Set-valued analysis