Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces

DOI10.1007/s11075-015-0085-4zbMath1351.65022OpenAlexW2287475882MaRDI QIDQ312177

Tran T. A. Nghia, Heinz H. Bauschke, Yunier Y. Bello Cruz, Hung M. Pha, Shawn Xianfu Wang

Publication date: 14 September 2016

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-015-0085-4

zbMATH Keywords

convergence accelerationlinear convergenceFriedrichs angleprincipal angleconvergent and semi-convergent matrixgeneralized Douglas-Rachford methodnumerical experimental resultsrelaxed alternating projection method

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical mathematical programming methods (65K05) Convex programming (90C25) Iterative numerical methods for linear systems (65F10)

Related Items (23)

Circumcentering the Douglas-Rachford method ⋮ Local convergence properties of Douglas-Rachford and alternating direction method of multipliers ⋮ On the circumcentered-reflection method for the convex feasibility problem ⋮ The optimal error bound for the method of simultaneous projections ⋮ On the linear convergence of the circumcentered-reflection method ⋮ Tight global linear convergence rate bounds for Douglas-Rachford splitting ⋮ Polynomial estimates for the method of cyclic projections in Hilbert spaces ⋮ Convergence rates for the relaxed Peaceman-Rachford splitting method on a monotone inclusion problem ⋮ The block-wise circumcentered-reflection method ⋮ Comparing the methods of alternating and simultaneous projections for two subspaces ⋮ 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 ⋮ Unmatched Projector/Backprojector Pairs: Perturbation and Convergence Analysis ⋮ A generic online acceleration scheme for optimization algorithms via relaxation and inertia ⋮ Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. II: Mean-square and linear convergence ⋮ On the optimal relaxation parameters of Krasnosel'ski–Mann iteration ⋮ Local linear convergence analysis of Primal–Dual splitting methods ⋮ Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces ⋮ Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators ⋮ The circumcentered-reflection method achieves better rates than alternating projections ⋮ Error bounds for the method of simultaneous projections with infinitely many subspaces ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections

Uses Software

• gnuplot
• UNLocBoX
• Julia

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterative methods for fixed point problems in Hilbert spaces
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Semi-convergence and relaxation parameters for a class of SIRT algorithms
• Reflection-projection method for convex feasibility problems with an obtuse cone
• Generalizations of the projection method with applications to SOR theory for Hermitian positive semidefinite linear systems
• Error bounds for the method of alternating projections
• On principal angles between subspaces in \(\mathbb{R}^n\)
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Acceleration schemes for the method of alternating projections
• Comparison theorems for the convergence factor of iterative methods for singular matrices
• On square roots of \(M\)-operators
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Extrapolation algorithm for affine-convex feasibility problems
• Infinite powers of matrices and characteristic roots
• Matrix Algorithms
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• Proximal Splitting Methods in Signal Processing
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Relaxed Alternating Projection Methods
• Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
• On Diagonally Relaxed Orthogonal Projection Methods
• A cycle-based bound for subdominant eigenvalues of stochastic matrices
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems
• Accelerating the convergence of the method of alternating projections
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• On Projection Algorithms for Solving Convex Feasibility Problems
• Numerical Methods for Computing Angles Between Linear Subspaces
• Comparison of Convergence of General Stationary Iterative Methods for Singular Matrices
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• The method of projections for finding the common point of convex sets
• Convex analysis and monotone operator theory in Hilbert spaces
• Best approximation in inner product spaces

This page was built for publication: Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces