PaperlayerView exact revision on arXiv

Source-linked AI summary

Acceleration of the Method of Alternating Projections on subspaces by GMRES

Luis Manuel Hernández-Ramos, Maryam Calles-Cabriles, Gorka Emaldi-Porco

arXiv:2610.36938v1math.NAcs.NA

TL;DR

MAP can converge slowly when subspace angles are small, motivating acceleration. The paper applies GMRES to MAP for subspaces and proves convergence to the best approximation; experiments on saddle-point problems compare its performance with other accelerations.

Abstract

from arXiv · show

In this paper we propose a GMRES-accelerated version of the Method of Alternating Projections (MAP) for subspaces. It is proved that the accelerated version not only converges to a feasible solution, but also solves a best approximation problem. Comparisons are made with other accelerations proposed in the literature, for solving saddle point problems.

Introduction

MAP finds the best approximation to a point in the intersection of closed subspaces, but can converge slowly when the subspace angles are small. The paper proposes GMRES acceleration for MAP in R^n and establishes that it converges to the best approximation.

Introduction

  • The MAP iteration successively projects onto each subspace and converges to the orthogonal projection of the initial point onto their intersection.The paper describes MAP as a fixed-point scheme for the product of the projection operators.Source: Introduction · pp. 2–3
  • MAP can converge slowly in practice when the angles between the involved subspaces are small.Source: Introduction · p. 2
  • The proposed GMRES acceleration applies to the MAP operator in R^n without symmetrizing it, unlike the cited CG approach, which requires a self-adjoint operator.The paper compares it with CG acceleration of the symmetrized Cimmino operator and randomized Kaczmarz accelerations.Source: Introduction · p. 3

Method of Alternating Projections Acceleration by Solving (Singular) Linear Systems

  • When the intersection contains nontrivial feasible points, A = I −T is singular and non-symmetric; the homogeneous system remains consistent because zero is a solution.The paper invokes GMRES results for singular systems with N(A) = N(A^T), under which breakdown after reaching a least-squares solution is benign; here consistency makes that breakdown a Krylov-subspace degeneracy.Source: Method of Alternating Projections… · p. 4
  • GMRES applied to (I −T)x = 0 converges to PMx0, the best approximation of the initial iterate in the subspace intersection M.The theorem uses Fix T = Fix T^T = M, so N(I −T) = N(I −T^T).Source: Method of Alternating Projections… · p. 7
  • The implementable algorithm applies I −T through consecutive projections rather than constructing its matrix, then solves a small least-squares problem over the Krylov subspace.The algorithm uses the product of the projections to evaluate the operator action.Source: Method of Alternating Projections… · pp. 7–8

Numerical Experiments

The experiments compare GMRES-accelerated MAP with other projection-method accelerations on saddle-point problems, formulated as best-approximation problems in the A inner product. GMRES outperforms classical MAP and MAP-CG in almost all Group 1 problems, while Group 2 runtime comparisons show no clear winner between MAP-GMRES and Cimmino-GC.

Numerical Experiments

  • The experiments use A-projections, stop when the A-norm of the residual reaches 10^-6, and apply an augmented-Lagrangian technique to improve behavior and ensure A is positive definite.The upper-left block also receives 0.01 times the identity to improve its condition number.Source: Numerical Experiments · p. 9, Results · p. 10

Saddle point problems resolution by MAP

  • Under the stated hypotheses, the saddle-point solution is the A-orthogonal projection of A^-1f onto the intersection of the constraint kernels.This casts the problem as a best-approximation problem solvable by MAP; projections onto individual kernels can be computed through smaller saddle-point problems.Source: Saddle point problems resolution by MAP · pp. 9–10

Results

  • The proposed acceleration is compared in Group 1 with the classical von Neumann–Halperin method (MAP) and conjugate-gradient-based acceleration; Group 2 comparisons include the Greedy Randomized Kaczmarz method proposed in.Source: Results · pp. 10–11

Results for the Group 1

Results for the Group 2

  • Group 2 comparisons show no clear winner in projection counts or average runtime between MAP-GMRES and Cimmino-GC.The Greedy Kaczmarz projection and runtime values are averages over 500 runs.Source: Results for the Group 2 · p. 11, Table 2 · p. 14

Final remarks

The authors report that MAP-GMRES outperforms symmetrized-operator Conjugate Gradients and usually runs faster than Kaczmarz Greedy, while remaining competitive with Cimmino on some problems.

Final remarks

  • MAP-GMRES outperforms the symmetrized-operator Conjugate Gradients approach proposed in.Source: Final remarks · p. 15
  • MAP-GMRES has better runtime performance than Kaczmarz Greedy in most cases.Source: Final remarks · p. 15
  • MAP-GMRES is competitive with Cimmino acceleration using conjugate gradients for some problems, while Cimmino is more parallelizable by nature.Source: Final remarks · p. 15

Related papers

Loading 2610.36938v1…