Accuracy of approximate projection to the semidefinite cone

Nikitas Rontsis; Paul J. Goulart; Yuji Nakatsukasa

REVIEW 2 major objections 4 minor 20 references

Accuracy of approximate projection to the semidefinite cone

T0 review · 2 major / 4 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 This paper proves that small spectral gaps do not impair the accuracy of approximate projections onto the positive semidefinite cone, replacing inverse-gap bounds with a computable residual bound.

desk verdict A genuinely gap-independent projection bound with correct proofs, but the introduction's clean √2 statement needs the D≼0 condition and is otherwise false. read the letter →

arxiv 1908.01606 v2 pith:5OGAEJJE submitted 2019-08-05 math.NA cs.NA

Paul J. Goulart , Yuji Nakatsukasa , Nikitas Rontsis This is my paper · ORCID

classification math.NAcs.NA MSC 65F1515A4515B4890C22

keywords positivesemidefiniteconeprojectionerrorgap-independentboundRayleigh-RitzresidualmatrixnearnessprogrammingFrobeniusnorm

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

Small spectral gaps are not a threat to the accuracy of approximate projections onto the positive semidefinite cone. The paper proves a Frobenius-norm error bound in which the projection error is controlled by the computable residual $R=A\hat V-\hat V\hat\Lambda$, with no factor proportional to the inverse gap: in the clean case $\|\hat V\hat\Lambda\hat V^T-\Pi_+(A)\|_F\le\sqrt{2}\|R\|_F$, and in the general case an extra term $\|D_+\|_F$ appears. This matters because such projections are the inner-loop workhorse of semidefinite programming methods and eigensolver-based routines, and a gap-independent, residual-based bound turns an unknown quantity into a computable stopping criterion. The paper also bounds the related measure $\|A(V_+V_+^T-\hat V\hat V^T)\|_F$ and shows the two accuracy measures stay within $\|R\|_F$ of each other.

What carries the argument

The central mechanism is the nonexpansiveness of the metric projection onto the semidefinite cone in the Frobenius norm: $\|\Pi_+(B)-\Pi_+(A)\|_F\le\|B-A\|_F$. The proof constructs an auxiliary matrix $B=\hat V\hat\Lambda\hat V^T+\hat V_\perp\Pi_-(\hat V_\perp^T A\hat V_\perp)\hat V_\perp^T$, chosen so that $\Pi_+(B)=\hat V\hat\Lambda\hat V^T$, and then a unitary congruence rewrites $\|B-A\|_F$ in terms of the residual blocks. Section 3 gives a first-principles derivation that exposes the cancellation responsible for gap-independence: the sine of the angle between $\hat V$ and a positive eigenvector $v_i$ enters with a factor $1/\lambda_i$, and multiplication by the eigenvalue $\lambda_i$ in the projected error cancels it, so no gap denominator survives.

What would settle it

Take a small symmetric matrix $A$ with eigenvalues straddling zero, compute a Rayleigh-Ritz pair $(\hat V,\hat\Lambda=\hat V^T A\hat V)$ with $\hat\Lambda\succeq 0$ and with $\hat V_\perp^T A\hat V_\perp\preceq 0$, and evaluate the ratio $\|\hat V\hat\Lambda\hat V^T-\Pi_+(A)\|_F/\|R\|_F$. The theorem forces this ratio never to exceed $\sqrt{2}$; a single example exceeding $\sqrt{2}$, or a sequence of small-gap examples where the ratio grows as the gap shrinks, would refute the gap-independence claim. For the paper's spectral-norm conjecture, a numerical search for matrices with $\|\hat V\hat\Lambda\hat V^T-\Pi_+(A)\|_2>2\|R\|_2$ would settle the conjectured constant.

Watch

Extended reading notes

Core claim

The paper establishes that, for a symmetric or Hermitian matrix $A$ and any orthonormal $\hat V$ with $\hat\Lambda\succeq 0$, $$\|\hat V\hat\Lambda\hat V^T-\Pi_+(A)\|$_F^{2}$\le\|R\|$_F^{2}$+\|\hat V_\perp^T A\hat V\|$_F^{2}$+\|D_+\|$_F^{2}$,$$ where $R=A\hat V-\hat V\hat\Lambda$ and $D_+=\Pi_+(\hat V_\perp^T A\hat V_\perp)$. If the approximate eigenpairs come from the Rayleigh-Ritz process, $\hat\Lambda=\hat V^T A\hat V$, and if the compression of $A$ to the orthogonal complement is negative semidefinite, the bound reduces to $\|\hat V\hat\Lambda\hat V^T-\Pi_+(A)\|_F\le\sqrt{2}\|R\|_F$. The spectral gap is absent from every one of these inequalities. The paper further proves $\|A(V_+V_+^T-\hat V\hat V^T)\|_F\le\sqrt{2}(\|R\|_F+\|D_+\|_F)$ and shows that this alternative measure of projection accuracy differs from the projected-matrix error by at most $\|R\|_F$.

Load-bearing premise

The load-bearing premise is that the approximate eigenpairs are computed with nonnegative Ritz values and that the part of $A$ in the orthogonal complement is non-positive (or nearly so); if that fails the residual alone no longer controls the error, and an extra correction term $\|D_+\|_F$ appears.

Editorial extensions

If this is right

Any backward-stable symmetric eigensolver yields projection error $O(u)\|A\|_F$ in the Frobenius norm even when $A$ has eigenvalues of tiny magnitude on both sides of zero.
Inexact projections computed to tolerance $\epsilon$ inside iterative methods such as ADMM carry a guaranteed projection error $O(\epsilon)\|A\|_F$, independent of the spectrum.
The residual $\|R\|_F$, which is already computed during Rayleigh-Ritz iterations, serves as a certified a posteriori error estimator for the projection, with no need to estimate spectral gaps.
The negative-eigenpair formulation extends the same guarantee to nearly positive definite matrices, where the projection is best computed from the small negative part rather than the large positive part.
The two accuracy measures--error of the projected matrix and $\|A(V_+V_+^T-\hat V\hat V^T)\|_F$--differ by at most $\|R\|_F$, so a bound on either transfers to the other.

Reading between the lines

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

Beyond the paper: the same two-ingredient proof (nonexpansive cone projection plus an auxiliary matrix isolating the opposite-sign part of $A$) should yield gap-independent bounds for projections onto other closed convex cones with Frobenius-nonexpansive projectors, such as the Lorentz cone; this is a testable extension the paper does not pursue.
Beyond the paper: the residual-only bound suggests a practical stopping rule for inner eigendecompositions in ADMM and proximal methods--terminate when $\|R\|_F$ falls below a target, with projection error guaranteed by the theorem rather than by gap estimation; the paper supplies the inequality but not the algorithm.
Beyond the paper: if the spectral-norm conjecture with constant $\delta=2$ is true, gap-independence would extend to the 2-norm, but the paper's own example shows $\Pi_+$ is not nonexpansive in that norm, so a proof would need a different mechanism than the one used here.

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

Short version: this is a real result with a presentation bug. The main theorems are correct, and the proof idea is elegant: nonexpansiveness of the convex projection plus a residual identity buys you a gap-independent Frobenius-norm error bound. But the headline inequality (7) as stated in the introduction is false without the extra condition V̂⊥ᵀAV̂⊥ ≼ 0. The stress-test counterexample is valid: A = diag(100,−1,−2), V̂ = [0.6,0.8,0]ᵀ, Λ̂ = 35.36 gives a projection error of about 93.3 while √2‖R‖ is about 68.6. The clean bound only follows from Corollary 2.2; Theorem 2.1 and Corollary 2.1 correctly include the extra ‖D₊‖ term. That is a genuine overstatement in the introduction, but it is a presentation problem, not a hole in the mathematics.

What is actually new: the gap-independent Frobenius bound for approximate PSD projections, the extension of Lemma 2.1 to all unitarily invariant norms, and the first-principles derivation in Section 3 that shows the λᵢ and 1/λᵢ cancellation explicitly. That last piece is the most valuable part of the paper—it explains why small gaps do not hurt accuracy. The experiments are consistent with the theory and are honestly reported; the spectral-norm case is correctly labeled a conjecture. The self-citation [15] appears only in a footnote for sharp Ritz bounds, which is fine.

Soft spots, in proportion: the introduction oversells (7) and should either state the D≼0 hypothesis or present the bound with the D₊ term. That is a real flaw, but the loaded theorems have the right hypotheses. The notation is dense in places, and Example 2.1 could use a sentence more of context. The proof of Lemma 4.1 is hard to follow but appears correct. Nothing here is a dealbreaker.

This paper is for anyone doing inexact projections in ADMM/SDP solvers or working on matrix nearness problems. I would cite it, and I would send it to peer review. A serious referee will want the introduction fixed, but the core contribution is solid and deserves to be in the literature.

Referee Report

2 major / 4 minor

Summary. The paper studies the accuracy of approximate projections onto the positive semidefinite cone. Given a symmetric matrix A with positive eigenpairs (V₊, Λ₊) and an approximate projector V̂Λ̂V̂ᵀ with residual R = AV̂ − V̂Λ̂, the authors derive upper bounds on the Frobenius-norm projection error that do not depend on the spectral gap. The main technical results are Theorem 2.1, which bounds the error by the square root of ‖R‖²_F + ‖V̂⊥ᵀAV̂‖²_F + ‖Π₊(V̂⊥ᵀAV̂⊥)‖²_F, and its corollaries, which simplify under the Rayleigh–Ritz relation or when V̂⊥ᵀAV̂⊥ is negative semidefinite, giving the clean √2‖R‖_F bound. Section 3 proves an analogous bound for the alternative measure A(V₊V₊ᵀ − V̂V̂ᵀ), and Section 4 reports numerical experiments supporting the gap-independence.

Significance. If the advertised bounds are valid under the stated hypotheses, the paper provides a practical, computable a posteriori error estimate for approximate semidefinite projections and convincingly demonstrates that small spectral gaps do not inherently compromise accuracy. The proofs are concise and rely on standard tools—nonexpansiveness of convex projections, residual algebra, and elementary norm identities. The sharpness example (Example 2.1) is valuable, and the numerical experiments illustrate the usefulness of the bounds in an ARPACK setting. However, the central advertised inequality (7) is stated without a necessary hypothesis, and Section 3's main theorem omits an assumption used in its proof; these issues require correction.

major comments (2)

[Introduction, Eq. (7)] Inequality (7) as stated in the introduction is false. The clean bound ‖V̂Λ̂V̂ᵀ − Π₊(A)‖_F ≤ √2‖R‖_F is only proven in Corollary 2.2 under the additional hypothesis V̂⊥ᵀAV̂⊥ ≼ 0 (i.e., D₊ = 0). Without that condition, Theorem 2.1 and Corollary 2.1 yield the weaker estimate with the extra term ‖D₊‖_F. This is not merely a formal gap: take A = diag(100, −1, −2), V̂ = [0.6, 0.8, 0]ᵀ, and Λ̂ = V̂ᵀAV̂ = 35.36. Here Λ̂ has the same size as Λ₊ and is positive definite, but ‖V̂Λ̂V̂ᵀ − Π₊(A)‖_F ≈ 93.3 while √2‖R‖_F ≈ 68.6, so (7) fails. The introduction should either state (7) with the D≼0 condition explicitly or promote Theorem 2.1/Corollary 2.1 (with the D₊ term) as the main general result.
[Section 3, Theorem 3.1] The statement of Theorem 3.1 says 'Under the notation and assumptions in Theorem 2.1', but the proof relies crucially on the Rayleigh–Ritz relation Λ̂ = V̂ᵀAV̂, which is not part of Theorem 2.1's assumptions. Indeed, the text immediately before Theorem 3.1 states 'In what follows we assume Λ̂ is obtained by the Rayleigh–Ritz process'. Without this assumption, the bound (23) need not hold, because the residual block structure in (24) and the estimates (25)–(27) use the relation. The theorem statement should include Λ̂ = V̂ᵀAV̂ as a hypothesis.

minor comments (4)

[Section 2, Eq. (13)] In the proof of Theorem 2.1, the off-diagonal blocks of the matrix in (13) appear to have sign errors relative to the definitions of B and R; the Frobenius norm is insensitive to these sign changes, so the proof remains valid, but the equation should be checked for consistency.
[Introduction, statement of (7)] The phrase 'which holds when Λ̂ has the same size as Λ₊' after (7) is misleading: the condition for the clean bound is the negative semidefiniteness of V̂⊥ᵀAV̂⊥, not the equality of sizes. The size condition is part of the setup for the cleanest case but is not sufficient.
[Example 2.1] The ratio reported in Example 2.1 is for squared Frobenius norms; clarifying this would help readers avoid confusion with the unsquared constants in (7) and (16).
[Section 2.2] The conjecture about the spectral norm would be easier to interpret if the proposed constant δ were tied to a specific family of examples; currently the text only states δ > 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained and proceeds from residual algebra and the nonexpansiveness of the projection operator.

full rationale

The paper derives gap-independent error bounds for approximate projections onto the semidefinite cone. The main results (Theorem 2.1, Corollaries 2.1–2.3, and Theorem 3.1) follow from residual algebra, the Rayleigh–Ritz relation Λ̂ = V̂ᵀAV̂ when invoked, and the nonexpansiveness of the projection operator in the Frobenius norm, cited to an external textbook [1, Proposition 4.16]. No parameter is fitted to data and then renamed as a prediction; the bounds explicitly express the projection error in terms of the computable residual norm ‖R‖_F and the auxiliary term ‖D₊‖_F. The clean inequality (7) is presented as a special case under stated hypotheses that include V̂⊥ᵀAV̂⊥ ≼ 0 (Corollary 2.2), and the introduction’s phrasing omits that condition, but this is a correctness/statement-precision issue, not circularity. The single self-citation [15] by coauthor Nakatsukasa appears only in a footnote about sharp Ritz vector bounds and is not used to justify the main theorem. The proof of Lemma 2.1 rests on a standard matrix inequality from Horn and Johnson. Overall, the derivation is self-contained: every bound is obtained by explicit algebraic manipulation from the stated assumptions, with no load-bearing self-referential premise.

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

The central claim rests only on standard convex analysis and linear algebra theorems, plus the definition of the residual R. There are no free parameters, no ad hoc assumptions, and no new entities. The only structural assumptions (PSD \hΛ, Frobenius norm) are stated as theorem hypotheses.

assumptions (4)

standard math Nonexpansiveness of projection onto a closed convex set in a Hilbert space (Frobenius norm)
Invoked in Theorem 2.1 and Section 2 as [1, Proposition 4.16]; this is a standard theorem in convex analysis.
standard math Majorization inequalities for unitarily invariant norms
Used in Lemma 2.1 via [13, Corollary 7.4.9.3] to establish optimality of the closed-form projection for any unitarily invariant norm.
standard math Rayleigh-Ritz residual identities
Used in Corollary 2.1 and Theorem 3.1, e.g., the equivalence between ‖R‖_F and the off-diagonal block ‖\hV_⊥^T A \hV‖_F follows from (14).
standard math Eigenvalue interlacing and perturbation bounds for Hermitian matrices
Used in Lemma 4.1 through [16, Theorems 10.1.1 and 10.3.1] to compare the bounds after dropping Ritz pairs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Accuracy of approximate projection to the semidefinite cone." pith.science (2026). https://pith.science/paper/5OGAEJJE

@misc{pith2026190801606,
  author       = {Pith},
  title        = {Pith review of: Accuracy of approximate projection to the semidefinite cone},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5OGAEJJE}},
  note         = {Machine review of arXiv:1908.01606}
}

read the original abstract

When a projection of a symmetric or Hermitian matrix to the positive semidefinite cone is computed approximately (or to working precision on a computer), a natural question is to quantify its accuracy. A straightforward bound invoking standard eigenvalue perturbation theory (e.g. Davis-Kahan and Weyl bounds) suggests that the accuracy would be inversely proportional to the spectral gap, implying it can be poor in the presence of small eigenvalues. This work shows that a small gap is not a concern for projection onto the semidefinite cone, by deriving error bounds that are gap-independent.

Figures

Figures reproduced from arXiv: 1908.01606 by the authors.

**Figure 2.** Left: Convergence of the “exact” projection error [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[15]

Sharp error bounds for Ritz vectors and approximate singular vectors

Y. Nakatsukasa. Sharp error bounds for Ritz vectors and approximate singular vectors. arXiv 1810.02532, 2018

work page Pith review arXiv 2018
[1]

Bauschke and P

H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Publishing Company, Incorporated, 1st edition, 2011

work page 2011
[2]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Found. Trends Mach. Learn., 3(1):1–122, 2011

work page 2011
[3]

Davis and W

C. Davis and W. Kahan. The Rotation of Eigenvectors by a Perturbation. III. SIAM J. Numer. Anal. , 7(1):1–46, 1970

work page 1970
[4]

Davis, W

C. Davis, W. Kahan, and H. F. Weinberger. Norm-Preserving Dilations and their Applications to Optimal Error Bounds. SIAM J. Numer. Anal. , 19(3):445–469, 1982

work page 1982
[5]

I. S. Duﬀ, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices. Oxford University Press, 2017

work page 2017
[6]

Eckstein and D

J. Eckstein and D. P. Bertsekas. On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293–318, 1992

work page 1992
[7]

Fletcher

R. Fletcher. Practical Methods of Optimization; (Second Edition) . Wiley-Interscience, New York, NY, USA, 1987

work page 1987

Show all 20 references

[8]

Garstka, M

M. Garstka, M. Cannon, and P. J. Goulart. COSMO: A conic operator splitting method for convex conic problems. arXiv 1901.10887, 2019

1901 arXiv
[9]

G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 4th edition, 2013

2013
[10]

N. Higham. Matrix nearness problems and applications. Applications of Matrix Theory, 1989

1989
[11]

Higham, N

N. Higham, N. Strabic, and V. Sego. Restoring deﬁniteness via shrinking, with an application to correlation matrices with a ﬁxed block. SIAM Review, 58(2):245–263, 2016

2016
[12]

N. J. Higham. Computing the nearest correlation matrix-a problem from ﬁnance. IMA Journal of Numerical Analysis , 22(3):329–343, July 2002. 17

2002
[13]

R. A. Horn and C. R. Johnson. Matrix Analysis . Cambridge University Press, New York, NY, USA, 2nd edition, 2012

2012
[14]

Lehoucq, D

R. Lehoucq, D. Sorensen, and C. Yang. ARPACK Users’ Guide. Society for Industrial and Applied Mathematics, 1998

1998
[16]

B. N. Parlett. The Symmetric Eigenvalue Problem . Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1998

1998
[17]

Qi and D

H. Qi and D. Sun. A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix. SIAM J. Matrix Anal. Appl. , 28(2):360–385, June 2006

2006
[18]

Y. Saad. Numerical Methods for Large Eigenvalue Problems . Society for Industrial and Applied Mathematics, 2011

2011
[19]

Vandenberghe and S

L. Vandenberghe and S. Boyd. Semideﬁnite Programming. SIAM Review, 38(1):49–95, 1996

1996
[20]

Xiong, V

J. Xiong, V. Zolotov, and L. He. Robust extraction of spatial correlation. IEEE Trans- actions on Computer-Aided Design of Integrated Circuits and Systems , 26(4):619–631, April 2007. 18

2007

Pith tools

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

[1] [15]

Sharp error bounds for Ritz vectors and approximate singular vectors

Y. Nakatsukasa. Sharp error bounds for Ritz vectors and approximate singular vectors. arXiv 1810.02532, 2018

work page Pith review arXiv 2018

[2] [1]

Bauschke and P

H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Publishing Company, Incorporated, 1st edition, 2011

work page 2011

[3] [2]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Found. Trends Mach. Learn., 3(1):1–122, 2011

work page 2011

[4] [3]

Davis and W

C. Davis and W. Kahan. The Rotation of Eigenvectors by a Perturbation. III. SIAM J. Numer. Anal. , 7(1):1–46, 1970

work page 1970

[5] [4]

Davis, W

C. Davis, W. Kahan, and H. F. Weinberger. Norm-Preserving Dilations and their Applications to Optimal Error Bounds. SIAM J. Numer. Anal. , 19(3):445–469, 1982

work page 1982

[6] [5]

I. S. Duﬀ, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices. Oxford University Press, 2017

work page 2017

[7] [6]

Eckstein and D

J. Eckstein and D. P. Bertsekas. On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293–318, 1992

work page 1992

[8] [7]

Fletcher

R. Fletcher. Practical Methods of Optimization; (Second Edition) . Wiley-Interscience, New York, NY, USA, 1987

work page 1987