Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces

DOI10.1007/S11075-018-0608-XMaRDI QIDQ2274154zbMATH OpenOpenAlexFDO

Authors Francisco J. Aragón Artacho, Rubén Campoy

Publication date 19 September 2019

Published in Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

averaged alternating modified reflections methodbest approximation problemFriedrichs anglelinear convergencelinear subspaces

Mathematics Subject Classification ID

Rate of convergence, degree of approximation (41A25) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: The averaged alternating modified reflections (AAMR) method is a projection algorithm for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method can be seen as an adequate modification of the Douglas--Rachford method that yields a solution to the best approximation problem. In this paper we consider the particular case of two subspaces in a Euclidean space. We obtain the rate of linear convergence of the AAMR method in terms of the Friedrichs angle between the subspaces and the parameters defining the scheme, by studying the linear convergence rates of the powers of matrices. We further optimize the value of these parameters in order to get the minimal convergence rate, which turns out to be better than the one of other projection methods. Finally, we provide some numerical experiments that demonstrate the theoretical results.

Recommendations

• A new projection method for finding the closest point in the intersection of convex sets
• Computing the resolvent of the sum of maximally monotone operators with the averaged alternating modified reflections algorithm
• A strongly convergent reflection method for finding the projection onto the intersection of two closed convex sets in a Hilbert space
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces

Cites work

• A limit theorem for projections
• A new projection method for finding the closest point in the intersection of convex sets
• Alternating projection methods.
• Best approximation in inner product spaces
• Convex analysis and monotone operator theory in Hilbert spaces
• Error bounds for the method of alternating projections
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Functional Operators (AM-22), Volume 2
• Generalization of the Trotter-Lie formula
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Iterative methods for fixed point problems in Hilbert spaces
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Projection methods: an annotated bibliography of books and reviews
• Relaxed Alternating Projection Methods
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• The method of projections for finding the common point of convex sets
• The optimal error bound for the method of simultaneous projections
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

Cited in

(11)

• The circumcentered-reflection method achieves better rates than alternating projections
• Error bounds for the method of simultaneous projections with infinitely many subspaces
• Strengthened splitting methods for computing resolvents
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Computing the resolvent of the sum of maximally monotone operators with the averaged alternating modified reflections algorithm
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Comparing averaged relaxed cutters and projection methods: theory and examples
• Polynomial estimates for the method of cyclic projections in Hilbert spaces
• Comparing the methods of alternating and simultaneous projections for two subspaces
• A new projection method for finding the closest point in the intersection of convex sets
• Coordinate-update algorithms can efficiently detect infeasible optimization problems

Describes a project that uses

Uses Software

• Matplotlib

This page was built for publication: Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces

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