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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Exact worst-case convergence of alternating projections with a common interior ball

Zenodo (CERN European Organization for Nuclear Research)
Optimization and Variational Analysis
preprint

Exact worst-case convergence of alternating projections with a common interior ball

preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Optimization and Variational Analysis
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon