The circumcentered-reflection method achieves better rates than alternating projections

DOI10.1007/S10589-021-00275-6zbMATH Open1470.49058arXiv2007.14466OpenAlexW3046171782MaRDI QIDQ2044486FDOQ2044486

Authors: Reza Arefidamghani, Roger Behling, Luiz-Rafael Santos, Yunier Y. Bello Cruz, Alfredo Iusem 

Publication date: 9 August 2021

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: We study the convergence rate of the Circumcentered-Reflection Method (CRM) for solving the convex feasibility problem and compare it with the Method of Alternating Projections (MAP). Under an error bound assumption, we prove that both methods converge linearly, with asymptotic constants depending on a parameter of the error bound, and that the one derived for CRM is strictly better than the one for MAP. Next, we analyze two classes of fairly generic examples. In the first one, the angle between the convex sets approaches zero near the intersection, so that the MAP sequence converges sublinearly, but CRM still enjoys linear convergence. In the second class of examples, the angle between the sets does not vanish and MAP exhibits its standard behavior, i.e., it converges linearly, yet, perhaps surprisingly, CRM attains superlinear convergence.

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

Recommendations

• On the circumcentered-reflection method for the convex feasibility problem
• Circumcentering reflection methods for nonconvex feasibility problems
• Circumcentering the Douglas-Rachford method
• The block-wise circumcentered-reflection method
• Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces

zbMATH Keywords

alternating projectionsconvergence rateconvex feasibility problemcircumcentered-reflection method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Decomposition methods (49M27) Acceleration of convergence in numerical analysis (65B99)

Cites Work

• Error bounds for the method of alternating projections
• On Projection Algorithms for Solving Convex Feasibility Problems
• Title not available (Why is that?)
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Functional Operators (AM-22), Volume 2
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• Decomposition through formalization in a product space
• Convex analysis and monotone operator theory in Hilbert spaces
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Proximity Maps for Convex Sets
• Title not available (Why is that?)
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• Circumcentering the Douglas-Rachford method
• On the linear convergence of circumcentered isometry methods
• Circumcentered methods induced by isometries
• On the linear convergence of the circumcentered-reflection method
• On the circumcentered-reflection method for the convex feasibility problem
• On the constrained error bound condition and the projected Levenberg-Marquardt method
• Local convergence analysis of the Levenberg-Marquardt framework for nonzero-residue nonlinear least-squares problems under an error bound condition
• The block-wise circumcentered-reflection method
• On circumcenters of finite sets in Hilbert spaces
• On circumcenter mappings induced by nonexpansive operators

Cited In (11)

• A finitely convergent circumcenter method for the convex feasibility problem
• Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions
• A successive centralized circumcentered-reflection method for the convex feasibility problem
• Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections
• Bregman circumcenters: basic theory
• Finite convergence of locally proper circumcentered methods
• Circumcentering approximate reflections for solving the convex feasibility problem
• Circumcentering reflection methods for nonconvex feasibility problems
• Bregman circumcenters: monotonicity and forward weak convergence
• Circumcentric directions of cones
• On the centralization of the circumcentered-reflection method

This page was built for publication: The circumcentered-reflection method achieves better rates than alternating projections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044486)