PaperlayerView exact revision on arXiv

Source-linked AI summary

The rate of convergence in the method of alternating projections

Catalin Badea, Sophie Grivaux, Vladimir Muller

arXiv:1006.2047v1math.FAcs.NAmath.NA

TL;DR

The paper asks when products of projections converge quickly and uniformly rather than arbitrarily slowly. It analyzes these rates through operator and subspace criteria, including a generalized Friedrichs parameter. For cyclic products of orthogonal projections, it establishes the QUC/ASC dichotomy and characterizes QUC by that parameter.

Abstract

from arXiv · show

A generalization of the cosine of the Friedrichs angle between two subspaces to a parameter associated to several closed subspaces of a Hilbert space is given. This parameter is used to analyze the rate of convergence in the von Neumann-Halperin method of cyclic alternating projections. General dichotomy theorems are proved, in the Hilbert or Banach space situation, providing conditions under which the alternative QUC/ASC (quick uniform convergence versus arbitrarily slow convergence) holds. Several meanings for ASC are proposed.

1. Introduction

The paper moves from convergence of alternating projections to the question of its rate, extending the analysis from two subspaces to cyclic products of several subspaces. It develops quick-uniform versus arbitrarily-slow convergence criteria and several formulations of arbitrarily slow convergence.

1A. The method of alternating projections.

  • Halperin’s cyclic projection iterates converge strongly to the projection onto the intersection, while norm convergence for random products remains an open question.When every subspace occurs infinitely often in the random sequence, its weak limit is the projection onto the intersection.Source: 1A. The method of alternating… · pp. 1–2

1B. The rate of convergence.

  • For two subspaces, the Friedrichs angle characterizes geometric convergence, but for three or more, pairwise Friedrichs angles alone do not determine the error bound.When the sum of two subspaces is not closed, convergence is strong but not uniform and can be arbitrarily slow.Source: 1B. The rate of convergence · pp. 2–3

1C. What this paper is about.

  • The paper generalizes rate-of-convergence results to several subspaces, proving a quick-uniform versus arbitrarily-slow dichotomy and extending the Friedrichs cosine to that setting.It also gives error estimates and equivalent criteria, including criteria involving random products of projections.Source: 1C. What this paper is about · p. 3

1D. Conditions for arbitrarily slow convergence.

  • For strongly convergent operator iterates, the paper proves QUC/ASC dichotomies under operator conditions and gives several variants of arbitrarily slow convergence.The variants impose different orbit or dual-pairing bounds; in Hilbert spaces, the paper also proves the ASCH version.Source: 1D. Conditions for arbitrarily slow… · pp. 3–4

1E. A generalization of the Friedrichs angle.

The paper extends the Friedrichs cosine to a parameter for several subspaces and uses it to characterize convergence rates in cyclic alternating projections.

1E. A generalization of the Friedrichs angle.

  • The parameter c(M1, . . . , MN) extends the cosine of the Friedrichs angle to several subspaces and is used to quantify convergence rates.The paper also considers the configuration constant, inclination, and a Friedrichs angle between the product space and diagonal subspace.Source: 1E. A generalization of the Friedrichs… · p. 4
  • For pairwise orthogonal subspaces, c(M1, . . . , MN) = 0; its value 1 corresponds to arbitrarily slow cyclic alternating-projection convergence.Source: 1E. A generalization of the Friedrichs… · p. 4
  • The paper characterizes the QUC/ASC dichotomy using geometric properties, operator spectral properties, and random projection products, and estimates geometric convergence when c(M1, . . . , MN) < 1.Source: 1E. A generalization of the Friedrichs… · p. 4

2A. Dichotomy theorems.

The section establishes operator-theoretic conditions for a quick-uniform versus arbitrarily-slow convergence dichotomy. It relates quick uniform convergence to closedness of an operator range and extends the results under spectral and space assumptions.

2A. Dichotomy theorems.

  • For strongly convergent iterates of a bounded operator, either QUC or ASC1 holds, and QUC is equivalent to Ran(T − I) being closed.The ASC1 condition can be replaced by ASC2.Source: 2A. Dichotomy theorems · p. 5
  • For power-bounded mean-ergodic operators with spectrum in D ∪ {1}, the iterates converge strongly and the dichotomy includes ASC3, or ASCH when X is a Hilbert space.In these cases, QUC is equivalent to Ran(I − T) being closed.Source: 2A. Dichotomy theorems · p. 6
  • When QUC fails under the stated spectral assumptions, the proof uses absence of an isomorphic copy of c0 for ASC3 and a Hilbert-space result for ASCH.Source: 2A. Dichotomy theorems · p. 6

2B. Applications to the method of alternating projections.

The section applies the operator dichotomies to semigroups generated by projections, under specified geometric assumptions on the Banach space and projections.

2B. Applications to the method of alternating projections.

  • For T in the convex multiplicative semigroup generated by projections, strong convergence and the QUC/ASC variants follow under any of three stated Banach-space and projection conditions.The conditions include uniformly convex or uniformly smooth spaces with norm-one projections, or a reflexive space with the stated norm bound; hermitian projections satisfy that bound.Source: 2B. Applications to the method of… · p. 7
  • In the cited projection settings, the spectrum lies in D ∪ {1} and the iterates converge strongly, allowing the dichotomy theorems to apply.Source: 2B. Applications to the method of… · p. 7

3. A generalization of Friedrichs angle for N subspaces

For two closed subspaces, the convergence rate of alternating projections is controlled by the Friedrichs angle; this section introduces and studies a generalization for N subspaces.

  • For two closed subspaces, the convergence rate of alternating projections is controlled by the Friedrichs angle.Source: §3 · p. 7
  • The section introduces a generalization of the Friedrichs angle for N subspaces.Source: §3 · p. 7
  • The paper studies this generalized angle parameter for several closed subspaces.Source: §3 · p. 7

3A. Definition.

The section develops a generalization of the cosine of the Friedrichs angle for several closed subspaces. It begins from an equivalent definition of the two-subspace angle and introduces associated numbers.

3A. Definition.

  • The section seeks an equivalent definition of the two-subspace Friedrichs angle as a starting point for generalization.Source: 3A. Definition · p. 7
  • For an admissible pair of vectors, the proof establishes an upper bound by the Friedrichs angle, s ≤ c(M1, M2).Source: 3A. Definition · pp. 7–8
  • The section introduces a Dixmier number associated with N closed subspaces and their intersection.Source: 3A. Definition · p. 8

3B. Other parameters and properties of the Friedrichs number.

The section relates parameters for several subspaces to projections in a product Hilbert space and establishes bounds connecting the Friedrichs number, configuration constants, and inclination.

3B. Other parameters and properties of the Friedrichs number.

4A. A qualitative result.

Theorem 4.1 characterizes arbitrarily slow convergence through equivalent operator, spectral, geometric, and approximate-vector conditions. It also identifies quick uniform convergence with c(M1, . . . , MN) < 1.

4A. A qualitative result.

  • Ran(T − I) is not closed exactly when the theorem’s equivalent ASC conditions hold for T = PN · · · P1.The conditions also include spectral tests, approximate fixed vectors, and geometric conditions on the subspaces.Source: 4A. A qualitative result · p. 14
  • Random products have an ASC condition quantified over every index sequence and every positive sequence tending to zero.The theorem also relates the geometric condition to nonclosedness of a sum in HN−1.Source: 4A. A qualitative result · pp. 15, 19
  • The geometric criterion is c(M1, . . . , MN) = 1, equivalently κ(M1, . . . , MN) = 1 or ℓ(M1, . . . , MN) = 0.Equivalently, diag(M1) + M2 ⊕ · · · ⊕ MN is not closed in HN−1.Source: 4A. A qualitative result · pp. 15, 19
  • ASC also has spectral characterizations: the essential norm of T − PM equals 1, and 1 belongs to its essential spectrum.The theorem gives corresponding primed conditions for all finite products of the projections.Source: 4A. A qualitative result · p. 15
  • For every finite-codimensional closed K ⊂ M⊥, there are unit vectors in K with arbitrarily small distances to every Mj.This approximate-vector condition is one of the equivalent geometric characterizations.Source: 4A. A qualitative result · p. 15
  • QUC holds if and only if c(M1, . . . , MN) < 1; otherwise the dichotomy gives ASC in its stated senses.The theorem also gives a quantitative estimate for geometric convergence in terms of the Friedrichs number.Source: 4A. A qualitative result · p. 15

4B. Quantitative statements.

For cyclic alternating projections, the paper bounds the operator-norm error for projection orders that visit every subspace and distinguishes convergence behavior according to c(M1, …, MN).

4B. Quantitative statements.

4C. Comparison with other estimates.

The paper compares its multi-subspace parameter with pairwise angle conditions, showing how pairwise and sequential criteria relate to quick uniform convergence.

4C. Comparison with other estimates.

  • A Dixmier-angle cosine c_i,i+1 < 1 is sufficient for quick uniform convergence.Source: 4C. Comparison with other estimates · p. 21
  • If some pair i ≠ j has c_ij < 1, quick uniform convergence holds for the cyclic iterates, regardless of the projection order.Theorem 4.1 makes the QUC property invariant under permutations of the full projection order.Source: 4C. Comparison with other estimates · p. 21
  • A pairwise-cosine condition is stronger than c(M1, …, MN) < 1: all pairwise c_ij can equal 1 while the multi-subspace parameter is below 1.The example has c(M1, M2, M3) < 1 despite c_ij=1 for every pair.Source: 4C. Comparison with other estimates · p. 21
  • If each sequential cosine c_j=c(M1 ∩ ··· ∩ Mj−1, Mj) is below 1, then c(M1, …, MN) < 1.The proof gives ℓ(M1, …, MN) ≥ ℓ2 ··· ℓN and c(M1, …, MN) ≤ 1 − ℓ(M1, …, MN)^2.Source: 4C. Comparison with other estimates · p. 21
Loading 1006.2047v1…