The circumcentered-reflection method achieves better rates than alternating projections
From MaRDI portal
Publication:2044486
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.
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
Cites work
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- scientific article; zbMATH DE number 3029984 (Why is no real title available?)
- Circumcentered methods induced by isometries
- Circumcentering the Douglas-Rachford method
- Convex analysis and monotone operator theory in Hilbert spaces
- Decomposition through formalization in a product space
- Error bounds for the method of alternating projections
- Functional Operators (AM-22), Volume 2
- Local convergence analysis of the Levenberg-Marquardt framework for nonzero-residue nonlinear least-squares problems under an error bound condition
- On Projection Algorithms for Solving Convex Feasibility Problems
- On circumcenter mappings induced by nonexpansive operators
- On circumcenters of finite sets in Hilbert spaces
- On the circumcentered-reflection method for the convex feasibility problem
- On the constrained error bound condition and the projected Levenberg-Marquardt method
- On the convergence of von Neumann's alternating projection algorithm for two sets
- On the linear convergence of circumcentered isometry methods
- On the linear convergence of the circumcentered-reflection method
- Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
- Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
- Proximity Maps for Convex Sets
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
- The block-wise circumcentered-reflection method
Cited in
(11)- On the centralization of the circumcentered-reflection method
- 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
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)
