{"id":"d0ab5b8d-528c-4743-a23e-36920d1ccc55","arxiv_id":"1908.01606","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Rayleigh-Ritz approximations, the Frobenius-norm error of a PSD cone projection is at most sqrt(2) times the residual, independent of eigenvalue gaps.","lead":"The paper proves that the accuracy of approximate projections onto the positive semidefinite cone is bounded by a small multiple of the computable residual, with no dependence on the spectral gap. This removes a practical obstacle to using inexact projections inside iterative optimization methods such as ADMM.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised √2 bound omits the D≼0 condition; a matching-size PSD example violates (7).","rationale":"The reader accepted the paper with HIGH confidence, quoting (7) as the central result and stating that the clean bound holds when Λ̂ is PSD and compatibly sized. This misses the crucial D≼0 condition: even with PSD, same-sized Λ̂ and the Rayleigh–Ritz relation, the D₊ term can be nonzero and the clean √2 bound can fail, as the explicit example shows. The paper's formal theorems (Theorem 2.1, Corollaries 2.1–2.2) are correct and self-consistent; the issue is that the introduction and abstract advertise (7) without the full hypothesis set. Since the main theorems are sound but the headline claim is overstated, the appropriate disposition is to accept the paper conditional on correcting the statement of the main result to include the D≼0 condition or to present the general bound with D₊. The reader's weakest_assumption is partially aligned (it notes the importance of theorem hypotheses) but incorrectly attributes the extra term to failure of PSD of Λ̂ rather than to failure of D≼0. The central qualitative message—gap-independent accuracy—remains supported by the corrected bounds, so no rejection is warranted.","tokens_in":12335,"tokens_out":21197,"duration_ms":184432,"concrete_test":"Reproduce the counterexample: set A = diag(100, −1, −2), V̂ = [0.6, 0.8, 0]ᵀ, and Λ̂ = V̂ᵀAV̂ = 35.36. Compute R = AV̂ − V̂Λ̂, the true projection error ‖V̂Λ̂V̂ᵀ − Π₊(A)‖_F, and the quantities in Theorem 2.1. Verify that ‖V̂Λ̂V̂ᵀ − Π₊(A)‖_F > √2‖R‖_F, while the Theorem 2.1 bound (with ‖D₊‖_F = 63.64) holds. This directly settles whether inequality (7) is valid under only the size-and-PSD conditions stated in the introduction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's headline inequality (7), ‖V̂Λ̂V̂ᵀ−Π₊(A)‖_F ≤ √2‖R‖_F, is presented in the introduction as the main result, said to hold when Λ̂ has the same size as Λ₊. The rigorous support for this clean bound is Corollary 2.2, which requires the additional condition V̂⊥ᵀAV̂⊥ ≼ 0, i.e. D₊ = 0. Without it, Theorem 2.1 gives only ‖·‖_F² ≤ ‖R‖_F² + ‖V̂⊥ᵀAV̂‖_F² + ‖D₊‖_F², and Corollary 2.1 (with the Rayleigh–Ritz relation Λ̂ = V̂ᵀAV̂) gives ≤ 2‖R‖_F² + ‖D₊‖_F². The D₊ term is not automatically zero when Λ̂ is PSD and has the same size as Λ₊. A concrete counterexample to the unqualified statement (7) is A = diag(100, −1, −2), V̂ = [0.6, 0.8, 0]ᵀ, Λ̂ = V̂ᵀAV̂ = 35.36. Here k = 1 matches the number of positive eigenvalues, Λ̂ ≻ 0, and Λ̂ = V̂ᵀAV̂, but ‖V̂Λ̂V̂ᵀ − Π₊(A)‖_F ≈ 93.3 while √2‖R‖_F ≈ 68.6. The missing condition fails: V̂⊥ᵀAV̂⊥ has a positive eigenvalue of 63.64, so D₊ ≠ 0. Thus the introduction overstates the main result; the gap-independent bounds are correct but require either the D≼0 hypothesis (Corollary 2.2) or the extra D₊ term (Theorem 2.1/Corollary 2.1).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12736,"tokens_out":10297,"duration_ms":90777,"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":[{"comment":"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":"Introduction, Eq. (7)"},{"comment":"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.","section":"Section 3, Theorem 3.1"}],"minor_comments":[{"comment":"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.","section":"Section 2, Eq. (13)"},{"comment":"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.","section":"Introduction, statement of (7)"},{"comment":"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":"Example 2.1"},{"comment":"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.","section":"Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The main proofs of the paper are sound and the contribution is useful. My principal concern is the overstatement in Eq. (7), which is false as written and needs to be corrected before acceptance. The stress-test counterexample is valid and should be acknowledged. I would be willing to reconsider a revised version that addresses the two major comments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nThis 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.","headline":"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.","tokens_in":13260,"tokens_out":3184,"would_cite":true,"duration_ms":27994,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","15A45","15B48","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["positive semidefinite cone","projection error","gap-independent bound","Rayleigh-Ritz","residual bound","matrix nearness","semidefinite programming","Frobenius norm"],"falsifier":"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.","tokens_in":12150,"feed_emoji":"🧮","tokens_out":12761,"duration_ms":116870,"temperature":0.7,"pith_summary":"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.","feed_headline":"Eigenvalue gaps don't hurt PSD projection accuracy","feed_subtitle":"New gap-independent bounds tie projection error to a computable residual instead of an unknown gap.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the nonexpansiveness of the projection onto a closed convex set in the Frobenius norm, the key inequality behind Theorem 2.1.","marker":"[1]"},{"why":"The classical gap-dependent sin-theta bound that the paper contrasts and improves upon.","marker":"[3]"},{"why":"Provides the Rayleigh-Ritz and block-eigenvector decomposition identities used in Section 3's first-principles proof.","marker":"[9]"},{"why":"Background on matrix nearness problems and the known solution of the nearest-PSD problem for Frobenius and spectral norms.","marker":"[10]"},{"why":"Supplies the eigenvalue majorization inequality used to prove the minimizer property of $V_+\\Lambda_+V_+^T$ for every unitarily invariant norm.","marker":"[13]"},{"why":"Sharp Ritz-vector error bounds showing where the gap dependence enters, used to frame the motivating discussion.","marker":"[15]"},{"why":"Rayleigh-Ritz theory, including the interlacing theorem used in Lemma 4.1 for dropping unreliable Ritz pairs.","marker":"[16]"}],"fun_headline_variants":["Projection accuracy independent of eigenvalue gap","No gap needed: PSD projection errors shrink","Gap-free bounds for semidefinite projection","Small eigenvalues don't impair PSD projection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Projection accuracy independent of eigenvalue gap","No gap needed: PSD projection errors shrink","Gap-free bounds for semidefinite projection","Small eigenvalues don't impair PSD projection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000171,"raw_usage":{"total_tokens":1255,"prompt_tokens":911,"completion_tokens":344,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":288}},"tokens_in":527,"tokens_out":344,"duration_ms":3689,"temperature":1.0,"reasoning_tokens":288,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:07:29.238208+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bauschke and P","cited_arxiv_id":null,"evidence_quote":"Supplies the nonexpansiveness of the projection onto a closed convex set in the Frobenius norm, the key inequality behind Theorem 2.1."},{"cited_title":"Davis and W","cited_arxiv_id":null,"evidence_quote":"The classical gap-dependent sin-theta bound that the paper contrasts and improves upon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Rayleigh-Ritz and block-eigenvector decomposition identities used in Section 3's first-principles proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Background on matrix nearness problems and the known solution of the nearest-PSD problem for Frobenius and spectral norms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvalue majorization inequality used to prove the minimizer property of $V_+\\Lambda_+V_+^T$ for every unitarily invariant norm."},{"cited_title":"Sharp error bounds for Ritz vectors and approximate singular vectors","cited_arxiv_id":"1810.02532","evidence_quote":"Sharp Ritz-vector error bounds showing where the gap dependence enters, used to frame the motivating discussion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Rayleigh-Ritz theory, including the interlacing theorem used in Lemma 4.1 for dropping unreliable Ritz pairs."}],"review_version":1}