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

Friedrichs anglelinear convergencebest approximation problemlinear subspacesaveraged alternating modified reflections method

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• 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
• 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 Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• 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

Cited in

(10)

• A new projection method for finding the closest point in the intersection of convex sets
• Comparing the methods of alternating and simultaneous projections for two subspaces
• Strengthened splitting methods for computing resolvents
• 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
• The circumcentered-reflection method achieves better rates than alternating projections
• Polynomial estimates for the method of cyclic projections in Hilbert spaces
• Computing the resolvent of the sum of maximally monotone operators with the averaged alternating modified reflections algorithm
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Error bounds for the method of simultaneous projections with infinitely many subspaces

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)