Characterizing arbitrarily slow convergence in the method of alternating projections

DOI10.1111/J.1475-3995.2008.00682.XMaRDI QIDQ3563612zbMATH OpenOpenAlexFDO

Authors Heinz H. Bauschke, F. Deutsch, Hein S. Hundal

Publication date 31 May 2010

Published in International Transactions in Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

alternating projectionsangle between subspacescyclic projectionsorthogonal projectionsrate of convergence of the method of alternating projections

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Equations and inequalities involving linear operators, with vector unknowns (47A50) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Set-valued and variational analysis (49J53) Convex programming (90C25)

Abstract: In 1997, Bauschke, Borwein, and Lewis have stated a trichotomy theorem that characterizes when the convergence of the method of alternating projections can be arbitrarily slow. However, there are two errors in their proof of this theorem. In this note, we show that although one of the errors is critical, the theorem itself is correct. We give a different proof that uses the multiplicative form of the spectral theorem, and the theorem holds in any real or complex Hilbert space, not just in a real Hilbert space.

Recommendations

• scientific article; zbMATH DE number 3919670
• The rate of convergence for the method of alternating projections. II
• Another note on the von Neumann alternating projections algorithm
• The rate of convergence in the method of alternating projections
• An alternating projection that does not converge in norm

Cites work

• Error bounds for the method of alternating projections
• Functional Operators (AM-22), Volume 2
• scientific article; zbMATH DE number 3919670 (Why is no real title available?)
• scientific article; zbMATH DE number 1009689 (Why is no real title available?)
• scientific article; zbMATH DE number 3383043 (Why is no real title available?)
• On Projection Algorithms for Solving Convex Feasibility Problems
• On the convergence of von Neumann's alternating projection algorithm for two sets
• On the von Neumann alternating algorithm in Hilbert space
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• The rate of convergence for the cyclic projections algorithm. II: Norms of nonlinear operators
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• The rate of convergence for the method of alternating projections. II
• Theory of Reproducing Kernels
• What Does the Spectral Theorem Say?

Cited in

(32)

• Implicit error bounds for Picard iterations on Hilbert spaces
• The numerical range and the spectrum of a product of two orthogonal projections
• On the method of reflections
• Error bounds for the method of simultaneous projections with infinitely many subspaces
• Sequences of \(m\)-term deviations in Hilbert space
• Alternating projections, remotest projections, and greedy approximation
• On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• The optimal error bound for the method of simultaneous projections
• Ritt operators and convergence in the method of alternating projections
• Gearhart-Koshy acceleration for affine subspaces
• Weak limits of consecutive projections and of greedy steps
• The rate of convergence in the method of alternating projections
• Arbitrarily slow convergence of sequences of linear operators: a survey
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• scientific article; zbMATH DE number 3919670 (Why is no real title available?)
• Infinite products of arbitrary operators and intersections of subspaces in Hilbert space
• Weak, strong, and linear convergence of a double-layer fixed point algorithm
• Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections
• When products of projections diverge
• Analysis of the accuracy and convergence of equation-free projection to a slow manifold
• Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
• Slow convergence of sequences of linear operators. I: Almost arbitrarily slow convergence
• Slow convergence of sequences of linear operators. II: Arbitrarily slow convergence
• Polynomial estimates for the method of cyclic projections in Hilbert spaces
• Comparing the methods of alternating and simultaneous projections for two subspaces
• Alternating projections in CAT(0) spaces
• The geometry of monotone operator splitting methods
• Consecutive projections and greedy approximation in Hilbert space
• A generalization of the Friedrichs angle and the method of alternating projections
• Functions with prescribed best linear approximations
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets

This page was built for publication: Characterizing arbitrarily slow convergence in the method of alternating projections

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