The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle

DOI10.1016/j.jat.2014.06.002zbMath1307.49030arXiv1309.4709OpenAlexW2963899645MaRDI QIDQ2252928

Hung M. Phan, Heinz H. Bauschke, José Yunier Bello Cruz, Shawn Xianfu Wang, Tran T. A. Nghia

Publication date: 24 July 2014

Published in: Journal of Approximation Theory (Search for Journal in Brave)

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

zbMATH Keywords

linear convergencealternating projectionsconvex feasibility problemprojection operatorDouglas-Rachford splitting methodFriedrichs anglenormal cone operatorfirmly nonexpansive mappingreflector

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical optimization and variational techniques (65K10) Monotone operators and generalizations (47H05) Numerical methods based on nonlinear programming (49M37) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Decomposition methods (49M27)

Related Items

On the order of the operators in the Douglas-Rachford algorithm ⋮ On the Douglas-Rachford algorithm ⋮ On Slater's condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces ⋮ Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems ⋮ 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 Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging ⋮ Circumcentering the Douglas-Rachford method ⋮ Reflection Methods for Inverse Problems with Applications to Protein Conformation Determination ⋮ Dynamics of the Douglas-Rachford method for ellipses and \(p\)-spheres ⋮ Local convergence properties of Douglas-Rachford and alternating direction method of multipliers ⋮ On the circumcentered-reflection method for the convex feasibility problem ⋮ Affine nonexpansive operators, Attouch-Théra duality and the Douglas-Rachford algorithm ⋮ Convergence Rate Analysis of the Forward-Douglas-Rachford Splitting Scheme ⋮ On the linear convergence of the circumcentered-reflection method ⋮ Tight global linear convergence rate bounds for Douglas-Rachford splitting ⋮ Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions ⋮ Linear and strong convergence of algorithms involving averaged nonexpansive operators ⋮ The Douglas-Rachford algorithm for convex and nonconvex feasibility problems ⋮ Polynomial estimates for the method of cyclic projections in Hilbert spaces ⋮ Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems ⋮ Convergence rates for the relaxed Peaceman-Rachford splitting method on a monotone inclusion problem ⋮ The block-wise circumcentered-reflection method ⋮ On the centralization of the circumcentered-reflection method ⋮ Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency ⋮ Comparing the methods of alternating and simultaneous projections for two subspaces ⋮ How Averaged is the Composition of Two Linear Projections? ⋮ The Splitting Algorithms by Ryu, by Malitsky–Tam, and by Campoy Applied to Normal Cones of Linear Subspaces Converge Strongly to the Projection onto the Intersection ⋮ A successive centralized circumcentered-reflection method for the convex feasibility problem ⋮ A Lyapunov function construction for a non-convex Douglas-Rachford iteration ⋮ Fixed Point Analysis of Douglas--Rachford Splitting for Ptychography and Phase Retrieval ⋮ Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness ⋮ A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting ⋮ Fourier phase retrieval with a single mask by Douglas-Rachford algorithms ⋮ A three-operator splitting scheme and its optimization applications ⋮ A new projection method for finding the closest point in the intersection of convex sets ⋮ On the Finite Convergence of the Douglas--Rachford Algorithm for Solving (Not Necessarily Convex) Feasibility Problems in Euclidean Spaces ⋮ Local linear convergence analysis of Primal–Dual splitting methods ⋮ On the linear convergence of circumcentered isometry methods ⋮ Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces ⋮ Circumcentered methods induced by isometries ⋮ Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator ⋮ Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators ⋮ Linear convergence of the Douglas–Rachford method for two closed sets ⋮ The Douglas--Rachford Algorithm for Two (Not Necessarily Intersecting) Affine Subspaces ⋮ Error bounds for the method of simultaneous projections with infinitely many subspaces ⋮ Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis ⋮ Norm convergence of realistic projection and reflection methods ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ Reflection-based technique for synthesis of structured controllers with guaranteed local convergence ⋮ Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming

Uses Software

• Maple
• gnuplot
• Julia

Cites Work

• Attouch-Théra duality revisited: Paramonotonicity and operator splitting
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Functions with prescribed best linear approximations
• Error bounds for the method of alternating projections
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A cyclic Douglas-Rachford iteration scheme
• Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
• On Weak Convergence of the Douglas–Rachford Method
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Characterizing arbitrarily slow convergence in the method of alternating projections
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Accelerating the convergence of the method of alternating projections
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• On Projection Algorithms for Solving Convex Feasibility Problems
• Searching with iterated maps
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• New Demiclosedness Principles for (Firmly) Nonexpansive Operators
• Theory of Reproducing Kernels
• Convex analysis and monotone operator theory in Hilbert spaces
• Best approximation in inner product spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item