Exact worst-case convergence of alternating projections with a common interior ball
Unrefereed research candidate. In one sentence: this paper proves the Luner–Grimmer conjecture on the exact worst-case convergence of von Neumann's alternating projections when the two convex sets share an interior ball, in every dimension, and extends the exact answer to unequal balls, any number of projections, Hilbert space and the residual. Alternating projections (POCS in signal processing) look for a point in two convex sets by repeatedly moving to the nearest point of one set, then of the other. Suppose both sets contain a common ball of radius δ and the start lies within R of its centre. Luner and Grimmer (arXiv:2410.14811, versions 1 and 2, 2024) built two half-planes for which the distance to the intersection after N cycles equals max over 0 ≤ c ≤ κ of c2N−1(√(R2−δ2) − δ√((1+c)/(1−c))), with κ = 1 − 2δ2/R2, and conjectured that nothing is worse (Conjecture 6.2). Theorem 1 proves this upper bound for every N and in every dimension by a short hand-checkable argument: each trajectory is tracked by two numbers, compared with the half-plane trajectory through a monotone value function, and closed with a sharp error bound. Theorem 7 gives the exact worst case for balls of different radii about a common centre, after any number (at least two) of single projections, and in real Hilbert space; Theorem 8 gives the exact worst residual, which recovers the exact rate of Zamani and Glineur (2024) as δ → 0. Consequences include the sharp asymptotic R4κ2N/(8eδ2√(R2−δ2)N) and practical cycle counts: at R/δ = 10 and accuracy 10−3 the exact worst case needs 93 cycles, against 212 from an elementary bound with the sharp factor and 833 from the classical interior-point bound. The formula and the extremal half-planes are due to Luner and Grimmer; the contribution is the matching upper bound and the extensions. The archive contains the manuscript (PDF and Markdown source), figures with their data and plotting script, the PDF build script, four standard-library check suites (88,902 explicit exact-rational and high-precision checks, valid under python -O) with their recorded outputs, a verification record, a claim-by-claim AI index, the dated prior-art search, a rating-free internal review summary, Crossref records and a bibliography, CI and SHA-256 sums. Assurance: written proofs; the computations are finite checks, not proofs; internal AI-assisted review only (not peer review, independent reproduction or formal verification); bounded prior-art search. Open: three or more sets, relaxed projections, balls with different centres, smooth or strongly convex classes. Creator: Anonymous. Text, data and figures CC0-1.0; code MIT.
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-03
- DOI
- https://doi.org/10.5281/zenodo.23922445
- Primary Topic
- Optimization and Variational Analysis
- Type
- preprint