On the optimal error bound for the first step in the method of cyclic alternating projections

Ivan Feshchenko

On the optimal error bound for the first step in the method of cyclic alternating projections

T0 review · 0 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The worst-case first error in cyclic projections equals a matrix product maximum, and the three-subspace case is solved exactly.

desk verdict A clean, genuinely new result on the optimal first-step error in cyclic alternating projections, with a complete proof of the exact f_3 and a sharp first-order expansion near c=1. read the letter →

arxiv 1908.00531 v1 pith:42IAYDRH submitted 2019-08-01 math.FA

Ivan Feshchenko This is my paper · ORCID

classification math.FA MSC 46C0747B15

keywords cyclicalternatingprojectionsFriedrichsnumberDixmierorthogonalworst-caseerrorHermitianmatricespathgraphLaplacianrateofconvergence

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how large the first step of the method of cyclic alternating projections can be, in the worst case, when a cosine-like measure of the mutual position of n closed subspaces — the Friedrichs number — is bounded by c. It proves that the worst-case error is exactly the maximum of the product |a12 a23 ... a_{n-1,n}| over n×n Hermitian matrices with unit diagonal and 0 ≤ A ≤ (1+(n-1)c)I. From this equivalence the paper solves the three-subspace case completely: f_3(c)=$4c^{2}$ for c≤1/4 and f_3(c)=c for c≥1/4. For general n it obtains two-sided bounds whose linear coefficient near c=1 is 2(n-1) $sin^{2}$(π/(2n)), so the first-order behavior is sharp even though the exact f_n for n≥4 remains open. Knowing f_n matters because it converts directly into a bound on how quickly the alternating projection sequence approaches the intersection.

What carries the argument

The carrying object is the Hermitian matrix A with unit diagonal, understood as the Gram matrix of unit vectors v_1,...,v_n; the quantity Π(A)=|a_{12}a_{23}...a_{n-1,n}| is exactly the norm of the product of orthogonal projections onto the lines spanned by those vectors. The condition 0≤A≤(1+(n-1)c)I is shown to be equivalent to the Dixmier/Friedrichs number constraint, reducing an infinite-dimensional operator problem to a finite-dimensional semidefinite one. For the near-c=1 estimates the decisive inequality is a comparison of quadratic forms: sum_{i<j}(x_i-x_j)^2 ≤ D_n sum_{i=1}^{n-1}(x_i-x_{i+1})^2, whose sharp constant is controlled by the second eigenvalue λ_2 of the path graph Laplacian, λ_2(P_n)=4 $sin^{2}$(π/(2n)); together with the identity ||x_i-x_{i+1}||^2=||x_i||^2-||x_{i+1}||^2 for projected vectors, this yields the upper bound, and a perturbation along the corresponding eigenvector yields the matching lower bound.

What would settle it

For n=4, carry out a high-precision semidefinite optimization of |a12 a23 a34| over the reduced class H'_4(1+3c) for c=0.99, 0.999, 0.9999. The theorem predicts f_4(c)=1-a_4(1-c)+O((1-c)^2) with a_4=6 $sin^{2}$(π/8)≈0.87868; a fitted slope differing from a_4 beyond numerical error, or any subspace family achieving first-step error larger than the upper bound, would refute the claim. Alternatively, verify the unproved eigenvalue formula λ_2(P_4)=4 $sin^{2}$(π/8) directly, since Theorem 2.7 chooses the perturbation along that eigenvector.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 2.1: f_n(c) equals max{|a12 a23 ... a_{n-1,n}|} over Hermitian matrices A=(a_{ij}) with a_{ii}=1 and 0≤A≤(1+(n-1)c)I. The proof identifies such matrices with Gram matrices of unit vectors; the product of the first superdiagonal entries is exactly the norm of the product of projections onto the one-dimensional subspaces spanned by those vectors, and the upper/lower constraint on A encodes the condition c_D≤c. The paper then derives f_3(c)=$4c^{2}$ on [0,1/4] and f_3(c)=c on [1/4,1], with explicit optimal matrices, and shows that for c≤(n-1)^{-2} the exact formula f_n(c)=(n-1)^{n-1}$c^{{n-1}}$ holds. For all n it proves 1 - a_n(1-c) - \tilde b_n(1-c)^2 ≤ f_n(c) ≤ 1 - a_n(1-c) + b_n(1-c)^2, with a_n = 2(n-1) $sin^{2}$(π/(2n)) and b_n = 6(n-1)^2 $sin^{4}$(π/(2n)).

Load-bearing premise

The near-c=1 analysis stands on the unproved spectral fact that the path graph's second-smallest Laplacian eigenvalue is 4 $sin^{2}$(π/(2n)); if that number were different, the claimed slope a_n in both the upper and lower bounds would change.

Editorial extensions

If this is right

For three subspaces, the exact worst-case first-step error is known in closed form: 4c^2 for c≤1/4 and c for c≥1/4, so sharp three-iteration bounds become available.
For every n, f_n(c)=(n-1)^{n-1}c^{n-1} on [0,(n-1)^{-2}], giving exact small-Friedrichs-number behavior and an explicit optimal matrix in the reduced class.
For c close to 1, the first-order term of f_n(c) is exactly 2(n-1) sin^2(π/(2n))(1-c), so the previous square-root upper bounds are not first-order optimal; the new upper bound matches the lower bound to first order.
The functions f_n^{1/(n-1)} are concave, hence f_n is continuous, and f_n obeys a scaling relation f_n(1/((n-1)^2 c)) = f_n(c)/((n-1)^{n-1}c^{n-1}); these structural properties constrain any future exact solution for n≥4.
The optimal first diagonal (a12,a23,...,a_{n-1,n}) is unique whenever c>0, so the maximization problem has a well-defined answer even though f_n for n≥4 remains open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The matrix formulation turns f_n into a finite-dimensional semidefinite optimization problem; for n=4 one could run a numerical SDP solver to conjecture a closed form for f_4 and to test the functional equation numerically.
The appearance of the path graph Laplacian suggests that the second-order coefficient of f_n near c=1 may be expressible through other Laplacian eigenvalues, such as λ_3, which would be a natural extension the paper does not pursue.
Question 1 in the paper — whether f_n(c) ≤ 1 - a_n(1-c) for all c — is testable for n=3 using the exact f_3, since f_3(c)=c equals the linear bound; testing n=4 numerically would give evidence about whether the linear bound holds universally.
The functional equation gives a self-similar structure: iterating c ↦ 1/((n-1)^2 c) from the explicitly known small-c interval could generate many further points of f_n, potentially enough to pin down f_4 if combined with concavity and continuity.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Good paper, worth taking seriously. The genuinely new content is the matrix formulation (Theorem 2.1), the exact formula for f_3 (Theorem 2.2), the exact small-c value (Theorem 2.3), and the sharp first-order coefficient as c approaches 1. The earlier literature supplied upper bounds but not exact values or matching lower bounds, so this is a real advance in the subfield.

The hinge is Theorem 2.1, and the proof is solid in both directions. The direction from matrices to subspaces via Gram matrices is clean, and the reverse direction, using a clever chain of inner products to control the norm of the projection product, works. The reduction to real symmetric persymmetric matrices (Lemma 2.1) is also sound and simplifies the optimization.

The exact evaluation of f_3 is the centerpiece. The proof reduces to maximizing x^2 over a 3-by-3 matrix with one parameter y, and then uses the principal-minor criterion for positive semidefiniteness. The phrase “one can easily check” is doing a bit of work here; the inequalities are correct, but a referee might ask for a few more lines. This is a minor exposition issue, not a correctness issue.

For n>=4 the paper does not find f_n, and the author says so explicitly. The n=4 case is reduced to maximizing x^2 y with two free parameters, which is left open. That is an honest limitation, not a flaw.

The near-c=1 analysis rests on the spectral gap of the path Laplacian, lambda_2 = 4 sin^2(pi/(2n)). This is invoked as well-known and used in Lemma 3.1 and Theorem 2.7. It is an elementary fact and not a burden on the argument. The lower bound in Theorem 2.7 has a nonexplicit constant, so it proves optimality of the linear coefficient only up to quadratic error. That is fine, and the explicit upper bound matches the same linear coefficient.

No circularity, no fitting, no suspicious citation pattern. The paper is self-contained modulo standard facts, and the external references are used as comparisons, not as load-bearing inputs.

Who is this for? Specialists in alternating projections, operator theory, and numerical analysis who want the exact worst-case behavior of the first step, not the user looking for a new algorithm. It deserves a serious referee and, if the minor computations are verified, publication. I would be happy to see it in print after the author fills in the terse principal-minor verification and maybe says a bit more about the nonexplicit lower-bound constant.

Referee Report

0 major / 3 minor

Summary. The paper studies the worst-case first-step error of the method of cyclic alternating projections for n closed subspaces of a Hilbert space. It defines f_n(c) as the supremum of ||P_n...P_2P_1 - P_0|| over all n-tuples of subspaces whose Friedrichs number is at most c, and establishes that this supremum is exactly the matrix maximum of |a_{12}a_{23}...a_{n-1,n}| over Hermitian positive semidefinite matrices with unit diagonal and upper bound A <= (1+(n-1)c)I (Theorem 2.1). Using this equivalence, the paper obtains the exact value f_3(c) = 4c^2 for c in [0,1/4] and f_3(c)=c for c in [1/4,1] (Theorem 2.2), the exact small-c value f_n(c)=(n-1)^{n-1}c^{n-1} for c in [0,1/(n-1)^2] (Theorem 2.3), concavity of f_n^{1/(n-1)} and a functional equation (Theorems 2.4 and 2.5), and two-sided quadratic bounds near c=1 whose linear coefficient a_n = 2(n-1)sin^2(pi/(2n)) is sharp (Theorems 2.6 and 2.7).

Significance. If the results hold, the paper gives the first exact solution of the first-step worst-case problem for three subspaces and a sharp asymptotic first-order coefficient for all n, improving on the earlier bounds of Badea-Grivaux-Muller and Badea-Seifert. The matrix reformulation in Theorem 2.1 is elegant and likely to be a useful tool for further study of f_n for n>=4. The central proofs are complete and self-contained: the equivalence is proved in both directions, exact optima are exhibited with explicit matrices, and the near-c=1 lower bound is derived from a concrete family of one-dimensional subspaces. External results are used only as comparisons, and the paper ships no unexplained numerical or fitting steps. Overall this is a solid, well-motivated contribution to the theory of alternating projections.

minor comments (3)

[Section 3.11, Lemma 3.1] The proof invokes the spectral gap lambda_2(P_n)=4 sin^2(pi/(2n)) of the path Laplacian as 'well-known' without proof or a precise reference; since this fact is exactly what determines the sharp slope a_n, please add a short derivation or a concrete citation.
[Section 3.5, proof of Theorem 2.2] The passage from the principal-minor criterion to the displayed inequalities for x and y is compressed with 'one can easily check'; spelling out the 2x2 and 3x3 determinant conditions would make the proof easier to verify.
[Throughout] The manuscript contains numerous typographical and spacing artifacts (for example, 'metho d', 'orthog onal', 'Frie drichs', and 'n /greaterorequalslant4'); a careful proofreading pass is needed before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivation is self-contained and its external inputs are standard, non-load-bearing facts.

full rationale

The paper defines f_n geometrically as the worst-case first-step error of cyclic alternating projections, proves the equivalence to a Hermitian matrix optimization problem (Theorem 2.1), and then solves that optimization problem exactly for n=3 (Theorem 2.2) and in the small-c regime (Theorem 2.3). The upper and lower bounds around c=1 are derived from the same matrix formulation plus a quadratic-form inequality; none of these results is used as its own input. There is no fitted parameter renamed as a prediction, no definition that presupposes the target value, and no load-bearing self-citation: the cited results by Badea–Grivaux–Müller and Badea–Seifert are used only as known comparisons for the reader's orientation, not to justify the paper's claims. The only external mathematical fact invoked is the second eigenvalue of the path graph Laplacian, lambda_2(P_n) = 4 sin^2(pi/(2n)), used in Lemma 3.1 and in choosing the optimal angle perturbation in Theorem 2.7; this is a standard elementary spectral fact, stated as well-known rather than derived, and it does not encode the target result f_n or the paper's matrix maximum. Accordingly, the central derivation chain is self-contained and no circular step can be exhibited by quoting the paper's equations.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted: all constants a_n, b_n are explicitly defined, and ~b_n is an existential positive constant from the proof, not a fitted value. The paper introduces no new objects beyond the already-existing functions f_n and the matrix set H_n(t).

assumptions (4)

standard math The second smallest eigenvalue of the Laplacian of the path graph P_n is 4 sin^2(pi/(2n)).
Used in Lemma 3.1 to get the constant D_n and in Theorem 2.7 to minimize s2/s1. Cited as well-known without proof.
standard math A Hermitian matrix is positive semidefinite iff all principal minors are nonnegative.
Used in Theorem 2.2 to reduce the constraints 0<=A<=(1+2c)I to polynomial inequalities.
standard math For a Hermitian positive semidefinite matrix A, there exists a matrix B with A=B*B; columns of B give a Gram representation.
Used in the first half of Theorem 2.1 to realize a matrix as a system of one-dimensional subspaces.
standard math The operator norm of a Hermitian positive semidefinite matrix is its largest eigenvalue.
Used in the proof of Theorem 2.7 to compute ||P_1+...+P_n||.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the optimal error bound for the first step in the method of cyclic alternating projections." pith.science (2026). https://pith.science/paper/42IAYDRH

@misc{pith2026190800531,
  author       = {Pith},
  title        = {Pith review of: On the optimal error bound for the first step in the method of cyclic alternating projections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/42IAYDRH}},
  note         = {Machine review of arXiv:1908.00531}
}

abstract

Let $H$ be a Hilbert space and $H_1,...,H_n$ be closed subspaces of $H$. Set $H_0:=H_1\cap H_2\cap...\cap H_n$ and let $P_k$ be the orthogonal projection onto $H_k$, $k=0,1,...,n$. The paper is devoted to the study of functions $f_n:[0,1]\to\mathbb{R}$ defined by $$ f_n(c)=\sup\{\|P_n...P_2 P_1-P_0\|\,|c_F(H_1,...,H_n)\leqslant c\},\,c\in[0,1], $$ where the supremum is taken over all systems of subspaces $H_1,...,H_n$ for which the Friedrichs number $c_F(H_1,...,H_n)$ is less than or equal to $c$. Using the functions $f_n$ one can easily get an upper bound for the rate of convergence in the method of cyclic alternating projections. We will show that the problem of finding $f_n(c)$ is equivalent to a certain optimization problem on a subset of the set of Hermitian complex $n\times n$ matrices. Using the equivalence we find $f_3$ and study properties of $f_n$, $n\geqslant 4$. Moreover, we show that $$ 1-a_n(1-c)-\widetilde{b}_n(1-c)^2\leqslant f_n(c)\leqslant 1-a_n(1-c)+b_n(1-c)^2 $$ for all $c\in[0,1]$, where $a_n=2(n-1)\sin^2(\pi/(2n))$, $b_n=6(n-1)^2\sin^4(\pi/(2n))$ and $\widetilde{b}_n$ is some positive number.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Aronszajn, Theory of reproducing kernels , Trans

N. Aronszajn, Theory of reproducing kernels , Trans. Amer. Math. Soc. 68 (1950) 337–404

work page 1950
[2]

Badea, S

C. Badea, S. Grivaux, V. M¨ uller,A generalization of the Friedrichs angle and the method of al ternating projections, C. R. Math. Acad. Sci. Paris 348 (1-2) (2010) 53–56

work page 2010
[3]

Badea, S

C. Badea, S. Grivaux, V. M¨ uller, The rate of convergence in the method of alternating project ions, Algebra i Analiz 23 (3) (2011) 1–30

work page 2011
[4]

Badea, D

C. Badea, D. Seifert, Ritt operators and convergence in the method of alternating projections, J. Approx. Theory 205 (2016) 133–148

work page 2016
[5]

Deutsch, The method of alternating orthogonal projections

F. Deutsch, The method of alternating orthogonal projections . In: S.P. Singh (eds.) Approximation Theory, Spline Functions and Applications, NATO ASI Series (Series C : Mathematical and Physical Sciences), vol. 356, Springer, Dordrecht, 1992, pp. 105–121

work page 1992
[6]

Deutsch, The angle between subspaces of a Hilbert space

F. Deutsch, The angle between subspaces of a Hilbert space . In: S.P. Singh (eds.) Approximation The- ory, Wavelets and Applications, NATO Science Series (Series C: Math ematical and Physical Sciences), vol. 454, Springer, Dordrecht, 1995, pp. 107–130

work page 1995
[7]

Halperin, The product of projection operators , Acta Sci

I. Halperin, The product of projection operators , Acta Sci. Math. (Szeged) 23 (1962) 96–99

work page 1962
[8]

Kayalar, H

S. Kayalar, H. Weinert, Error bounds for the method of alternating projections , Math. Control Signals Systems 1 (1988) 43–59

work page 1988

Show all 10 references

[9]

Netyanun, D.C

A. Netyanun, D.C. Solmon, Iterated products of projections in Hilbert space , Amer. Math. Monthly 113 (7) (2006) 644–648

2006
[10]

von Neumann, Functional Operators—Vol

J. von Neumann, Functional Operators—Vol. II. The Geometry of Orthogonal S paces, Princeton University Press, Princeton, 1950 (a reprint of mimeographed lect ure notes ﬁrst distributed in 1933). Taras Shevchenko National University of Kyiv, F aculty of Mechanics and Mathematic...

1950

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Aronszajn, Theory of reproducing kernels , Trans

N. Aronszajn, Theory of reproducing kernels , Trans. Amer. Math. Soc. 68 (1950) 337–404

work page 1950

[2] [2]

Badea, S

C. Badea, S. Grivaux, V. M¨ uller,A generalization of the Friedrichs angle and the method of al ternating projections, C. R. Math. Acad. Sci. Paris 348 (1-2) (2010) 53–56

work page 2010

[3] [3]

Badea, S

C. Badea, S. Grivaux, V. M¨ uller, The rate of convergence in the method of alternating project ions, Algebra i Analiz 23 (3) (2011) 1–30

work page 2011

[4] [4]

Badea, D

C. Badea, D. Seifert, Ritt operators and convergence in the method of alternating projections, J. Approx. Theory 205 (2016) 133–148

work page 2016

[5] [5]

Deutsch, The method of alternating orthogonal projections

F. Deutsch, The method of alternating orthogonal projections . In: S.P. Singh (eds.) Approximation Theory, Spline Functions and Applications, NATO ASI Series (Series C : Mathematical and Physical Sciences), vol. 356, Springer, Dordrecht, 1992, pp. 105–121

work page 1992

[6] [6]

Deutsch, The angle between subspaces of a Hilbert space

F. Deutsch, The angle between subspaces of a Hilbert space . In: S.P. Singh (eds.) Approximation The- ory, Wavelets and Applications, NATO Science Series (Series C: Math ematical and Physical Sciences), vol. 454, Springer, Dordrecht, 1995, pp. 107–130

work page 1995

[7] [7]

Halperin, The product of projection operators , Acta Sci

I. Halperin, The product of projection operators , Acta Sci. Math. (Szeged) 23 (1962) 96–99

work page 1962

[8] [8]

Kayalar, H

S. Kayalar, H. Weinert, Error bounds for the method of alternating projections , Math. Control Signals Systems 1 (1988) 43–59

work page 1988