Accelerating the alternating projection algorithm for the case of affine subspaces using supporting hyperplanes

DOI10.1016/J.LAA.2014.11.035zbMATH Open1354.90142arXiv1406.4012OpenAlexW2963389134MaRDI QIDQ486223FDOQ486223

C. H. Jeffrey Pang

Publication date: 14 January 2015

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: The von Neumann-Halperin method of alternating projections converges strongly to the projection of a given point onto the intersection of finitely many closed affine subspaces. We propose acceleration schemes making use of two ideas: Firstly, each projection onto an affine subspace identifies a hyperplane of codimension 1 containing the intersection, and secondly, it is easy to project onto a finite intersection of such hyperplanes. We give conditions for which our accelerations converge strongly. Finally, we perform numerical experiments to show that these accelerations perform well for a matrix model updating problem.

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

Recommendations

• Accelerating the convergence of the method of alternating projections
• A new geometric acceleration of the von Neumann-Halperin projection method
• Acceleration schemes for the method of alternating projections
• Unconstrained optimization techniques for the acceleration of alternating projection methods
• An acceleration scheme for Dykstra's algorithm

zbMATH Keywords

alternating projectionsbest approximation problemsupporting hyperplanes

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonlinear programming (90C30) Best approximation, Chebyshev systems (41A50) Equations and inequalities involving linear operators, with vector unknowns (47A50) Iterative procedures involving nonlinear operators (47J25) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Linear Diophantine equations (11D04) Chains (nests) of projections or of invariant subspaces, integrals along chains, etc. (47A46)

Cites Work

• Acceleration schemes for the method of alternating projections
• Title not available (Why is that?)
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Title not available (Why is that?)
• The method of projections for finding the common point of convex sets
• Functional Operators (AM-22), Volume 2
• Title not available (Why is that?)
• An Algorithm for Restricted Least Squares Regression
• Title not available (Why is that?)
• Accelerating the convergence of the method of alternating projections
• Decomposition through formalization in a product space
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Extrapolation algorithm for affine-convex feasibility problems
• Theory and computations of some inverse eigenvalue problems for the quadratic pencil
• Two generalizations of Dykstra's cyclic projections algorithm
• Unconstrained Optimization Techniques for the Acceleration of Alternating Projection Methods
• Variable target value relaxed alternating projection method

Cited In (6)

• Accelerating the convergence of the method of alternating projections
• The Supporting Halfspace--Quadratic Programming Strategy for the Dual of the Best Approximation Problem
• Secant update generalized version of PSB: a new approach
• A symmetric grouped and ordered multi-secant Quasi-Newton update formula
• Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
• Acceleration schemes for the method of alternating projections

This page was built for publication: Accelerating the alternating projection algorithm for the case of affine subspaces using supporting hyperplanes

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