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

DOI10.1007/S11075-018-0608-XzbMATH Open1420.65027arXiv1711.06521OpenAlexW3101037765MaRDI QIDQ2274154FDOQ2274154

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

Publication date: 19 September 2019

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

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.

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

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

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)

Cites Work

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

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

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)