{"id":"cbf73b23-272e-4955-ad22-067edfaf2180","arxiv_id":"2607.19282","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For symmetric diagonally dominant matrices, the Nyström nuclear-norm error can violate diminishing returns, with minimal counterexamples in dimension three (four for nonempty base sets).","lead":"This paper shows that the diminishing-returns property of Nyström approximation errors, which holds for M-matrices, can fail for symmetric diagonally dominant matrices, and constructs the smallest possible counterexamples. It closes an open problem from a Simons workshop and clarifies the limits of greedy column selection.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"I read the paper in good faith. The main counterexample is explicit and reproducible: L(t) is SDD by construction, positive definite via its eigenvalues, and the four-point difference factors as (4.5). I spot-checked the t=2 case: det M(2)=(3)(17)=51, E(∅)=47/51, E({1})=E({2})=9/16, E({1,2})=1/5, giving Δ=-7/2040. The strict example L♯ also checks out. Minimality for n=2 follows from Proposition 5.3, and the nonempty-base lower bound n≥4 is airtight; L4 is a valid strict SDD complete-support example. The only places where the text is somewhat loose are the interpretation of the original problem and the Section 6 robustness statement, but neither affects the existence or minimality of the counterexamples. I therefore find no load-bearing flaw and would keep the ACCEPT verdict.","tokens_in":8722,"tokens_out":35082,"duration_ms":280883,"concrete_test":"Obtain the Simons workshop report arXiv:2602.05394v2 and check Problem 4.6's exact wording: confirm that 'diminishing returns' is defined as the four-point inequality (1.5) for all admissible A,i,j. If it instead refers only to consecutive marginal decreases or to a relative-error notion, the paper's claim to have completely resolved Problem 4.6 would require qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims of Theorem 1.1 are sound. The Schur-complement identity (2.2), the trace formulas (4.2)-(4.4), and the factorization (4.5) are internally consistent; the t=2 example reproduces the stated -7/2040. The minimality arguments (Proposition 5.3) and the nonempty-base embedding via L4 are also valid. Two caveats do not affect the mathematics: (i) the paper assumes Problem 4.6's 'diminishing returns' means exactly the inequality (1.5) for all admissible A,i,j; if the workshop intended a different notion, the 'complete answer' framing would need qualification. (ii) The robustness remark in Section 6 says both examples remain strictly diagonally dominant under sufficiently small perturbations; for the boundary example L(t) this is not literally true because L(t) is not strictly SDD, though nearby strict SDD counterexamples with negative Δ exist. Neither caveat undermines the counterexample or the minimality results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the nuclear-norm error of column-selected Nyström approximation for K=(L+γI)^{-1}, where L is symmetric diagonally dominant (SDD). It first proves a Schur-complement identity reducing the error to the trace of the inverse of the complementary principal submatrix, and an exact marginal formula. For SDDM (Stieltjes) matrices, it gives a self-contained proof that the inverse-trace function is supermodular, hence diminishing returns holds. The central contribution is a one-parameter SDD family L(t) in dimension three for which the four-point difference ΔE(∅;1,2) is negative on the sharp interval (1+√5)/2 < t < 1+√2. The paper proves that dimension three is minimal within the SDD class, that failure persists under strict diagonal dominance, that with a nonempty base set dimension four is minimal (via an explicit strictly SDD, complete-support example), and that greedy column selection can miss the optimal pair. It also includes a signature-switching criterion and a signed-cycle interpretation of the obstruction.","tokens_in":8924,"tokens_out":8681,"duration_ms":78332,"significance":"The result is significant: it resolves Problem 4.6 from a Simons workshop report by showing that, unlike the SDDM case, general SDD matrices do not guarantee diminishing returns for Nyström error. The counterexample is exact, with a sharp parameter interval, and the minimality proofs are clean. The paper gives explicit, verifiable trace formulas (e.g., Eq. (4.5) and the t=2 example producing -7/2040), and it provides a self-contained proof of the known SDDM result with due credit to prior work (Friedland–Gaubert, Atamtürk–Gómez, Chen–Wei). The signed-graph analysis and the greedy misselection example are valuable extras. If the result holds—and it appears sound—it closes an open question and clarifies the boundary between M-matrices and general diagonally dominant matrices.","major_comments":[],"minor_comments":[{"comment":"The robustness sentence states that 'both examples remain positive definite and strictly diagonally dominant under sufficiently small symmetric perturbations.' This is inaccurate for L(t) in (4.1), which is only SDD with equality in every row, not strictly SDD. The statement is correct for L♯ and L4. Please rephrase to say that L(t) can be perturbed to a strictly SDD matrix with a negative four-point difference, or restrict the strict-SDD robustness claim to the strictly SDD examples.","section":"Section 6"},{"comment":"The proof says 'Every difference with a nonempty base is nonnegative by Proposition 5.3,' but Proposition 5.3 appears later in Section 5. This forward reference is acceptable, but a brief pointer (e.g., 'see Section 5, Eq. (5.5)') would improve readability.","section":"Theorem 4.2"},{"comment":"The AI declaration says an AI system 'suggested L0.' It would be helpful to clarify whether this means the system proposed the specific matrix L0 during a numerical search, or whether it contributed only to editing; the current wording is slightly ambiguous. This does not affect the mathematics.","section":"AI declaration"},{"comment":"The proof of Corollary 5.2 invokes the strict example (4.9) to show failure for one signed triangle and then uses signature congruence. It may be worth explicitly noting that the signature switching preserves positive definiteness and the trace function, so the violation transfers to every pattern in the switching class.","section":"Section 5, Corollary 5.2"}],"recommendation":"minor_revision","confidential_remarks":"The paper's central claims are correct and well proved. The only substantive issue I found is the technically incorrect robustness remark in Section 6 regarding L(t) being strictly SDD under perturbation; this is easily fixed by rewording. The forward reference to Proposition 5.3 and the AI declaration wording are minor. I am not aware of any hidden circularity or unsupported claim. The paper is a strong contribution to the Nyström/submodularity literature and should be accepted after the minor revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper tells you exactly where the SDDM result stops: for general SDD matrices the Nyström error can fail supermodularity already in dimension three, and it gives the sharp parameter interval, minimality proofs, strict-SDD and nonempty-base counterexamples, and a signed-triangle explanation. The SDDM case was known, and the paper says so plainly and cites the right sources. The genuinely new content is the SDD obstruction family, the dimension minimality, and the greedy selection example.\n\nThe proofs are solid. The Schur-complement identity reduces the error to principal-inverse traces, the exact marginal formula in Lemma 2.2 is correct, the Neumann-series argument for Stieltjes matrices is clean, and the trace formulas for L(t), L#, and L4 reproduce the stated four-point differences. I spot-checked the algebra; the factorization of ΔE,t and the rational example at t=2 check out. The minimality argument via the terminal 2×2 stage is neat and rules out dimension two, and the embedding for nonempty base sets via L4 is legitimate, not a block-diagonal trick. The signature-switching/cycle criterion is a nice way to organize which sign patterns can be rescued.\n\nTwo soft spots, both minor. First, the paper assumes the workshop's “diminishing returns” means exactly the four-point inequality (1.5) for all admissible A,i,j. If Problem 4.6 intended a weaker notion (e.g., only consecutive additions or a relative-error definition), then the “complete answer” framing is stronger than what is proven. The paper states its convention explicitly, so this is a caveat about scope, not a flaw. Second, the robustness remark in Section 6 says both examples remain strictly SDD under sufficiently small perturbations. For L(t), which sits on the SDD boundary, that is not literally true; but L# provides the strict counterexample nearby, so the intended conclusion—failure is not a boundary artifact—holds. The wording should be tightened.\n\nThe citation pattern is honest, the AI declaration is transparent, and there is no fitting or post-hoc story. This is a modest but clean contribution: it closes the remaining SDD case of a named open problem with exact constructions and proves the dimension bounds. Anyone working on column subset selection or submodularity of inverse traces will want this. I would referee it without hesitation and recommend acceptance after a minor revision that fixes the robustness wording and, if possible, adds a sentence clarifying the interpretation of Problem 4.6.","headline":"Resolves the SDD half of a named open problem with exact, minimal counterexamples; the math is careful and the main caveat is interpretational, not technical.","tokens_in":9442,"tokens_out":1276,"would_cite":true,"duration_ms":16690,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F55","15B48","05C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Diagonal dominance alone cannot guarantee diminishing returns for Nyström error; a 3×3 matrix already breaks it.","keywords":["Nyström approximation","nuclear norm","column subset selection","supermodularity","symmetric diagonally dominant","M-matrix","signed graph","greedy selection"],"falsifier":"For the family (4.1), compute ΔE at t=1.60 and t=2.42; the claimed sharp interval ((1+√5)/2, 1+√2) ≈ (1.618, 2.414) predicts positivity outside. If any t outside this interval gives ΔE<0, the sharp interval is false. Alternatively, test the strict example L♯: direct computation should yield exactly −1/1092 for ΔE(∅;1,2).","tokens_in":8587,"feed_emoji":"📉","tokens_out":3945,"duration_ms":38181,"temperature":0.7,"pith_summary":"This paper settles an open question about whether the nuclear-norm error of column-selected Nyström approximation always diminishes at a decreasing rate when the underlying precision matrix is only symmetric diagonally dominant (SDD). The answer is no. The authors construct a one-parameter family of 3×3 SDD positive definite matrices for which the four-point difference is negative exactly on a sharp interval, identify the signed triangle as the cause, and prove that dimension three is minimal. They also show the failure persists for strictly diagonally dominant matrices and for nonempty base sets (dimension four), and that despite this, greedy column selection misses the optimal pair only by a bounded ratio.","feed_headline":"3×3 matrix kills diminishing-returns guarantee","feed_subtitle":"For diagonally dominant precision matrices, greedy column selection can miss the optimal pair; Nyström error is not supermodular.","key_machinery":"The Schur-complement identity E(S)=tr(M[S^c]^{-1}) reduces the Nyström error to traces of inverses of principal submatrices. The obstruction is generated by a signed triangle, where the 3×3 formula (5.2) shows the sign of ΔE depends on the effective coupling w=x−yz/c after eliminating the third coordinate; if w>0 but too small, failure occurs. Signature switching and the antibalanced-cycle criterion—every cycle has an even number of positive edges—mark the boundary between supermodular and failing realizations.","core_discovery":"For a positive definite SDD matrix L with γ>0 and M=L+γI, the Nyström error E(S)=tr(M[S^c]^{-1}) is strictly decreasing but not supermodular. The exact family L(t) in (1.7) has ΔE(∅;1,2)<0 precisely when (1+√5)/2<t<1+√2, so diagonal dominance cannot replace the sign condition in the Stieltjes/M-matrix case. A signed triangle—an odd cycle with two negative and one positive off-diagonal edges—creates a positive Schur-complement coupling w that is too weak to offset the indirect interaction, reversing the marginal inequality. Dimension two is safe, and with a nonempty base set, dimension four is minimal, even under strict diagonal dominance and complete support.","pith_inferences":["An approximate supermodularity inequality (e.g., a submodularity ratio bound) for SDD matrices would restore quantitative greedy guarantees; the paper leaves this open but shows the exact property fails.","The signed-graph viewpoint suggests a graph-theoretic classification problem in higher dimensions: which signed support graphs guarantee supermodular inverse traces for all positive definite realizations? This paper settles the converse only in dimension three.","The scaling behavior indicates the failure is robust to the shift parameter; one could test numerically whether the magnitude of the violation grows or decays with dimension for natural graph families, informing practical column-selection heuristics.","The explicit bounded greedy gap (6/5) could serve as a baseline for one-step-lookahead or local-search Nyström algorithms, which may recover optimality in the small examples while preserving performance on larger matrices."],"forward_implications":["The diminishing-returns property holds for SDDM matrices (Stieltjes case) and, more generally, for any positive definite matrix whose signed support graph is antibalanced, by signature switching.","Greedy column selection can uniquely pick the worst single column: for the SDD family, the best one-column choice {3} is contained in no optimal two-column set.","The counterexamples are stable under small perturbations and, by scaling (L,γ)→(αL,αγ), extend to any prescribed positive shift; the failure is not confined to the boundary of the SDD cone.","In dimension three, supermodularity of inverse traces for every positive definite realization of a fixed sign pattern holds if and only if the signed support graph is antibalanced.","The greedy misselection ratio remains bounded (6/5 in the strict example), so the failure is qualitative, not asymptotic; standard submodular-gain guarantees do not extend to SDD matrices."],"fun_headline_variants":["3×3 SDD matrix breaks Nyström error guarantee","Signed triangle causes Nyström error failure in 3D","Minimal 3D obstruction to Nyström supermodularity","Greedy column selection misses optimal Nyström pair","3×3 SDD family: diminishing returns fail"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The interpretation that the workshop's 'diminishing returns' question is exactly the four-point inequality (1.5) holding for all admissible sets and pairs; if the intended notion allowed only relative error or consecutive additions, the counterexamples would not be decisive. The constructions also rely on the standard definition of SDD and the fixed shift M=L+γI.","fun_headline_variants_meta":{"raw":{"variants":["3×3 SDD matrix breaks Nyström error guarantee","Signed triangle causes Nyström error failure in 3D","Minimal 3D obstruction to Nyström supermodularity","Greedy column selection misses optimal Nyström pair","3×3 SDD family: diminishing returns fail"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000513,"raw_usage":{"total_tokens":2347,"prompt_tokens":777,"completion_tokens":1570,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":1481}},"tokens_in":521,"tokens_out":1570,"duration_ms":11172,"temperature":1.0,"reasoning_tokens":1481,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T12:52:30.319624+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the family (4.1), compute ΔE at t=1.60 and t=2.42; the claimed sharp interval ((1+√5)/2, 1+√2) ≈ (1.618, 2.414) predicts positivity outside. If any t outside this interval gives ΔE<0, the sharp interval is false. Alternatively, test the strict example L♯: direct computation should yield exactly −1/1092 for ΔE(∅;1,2).","supporting_citations":[],"review_version":1}