Nystr\"om Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction

Matthew J. Colbrook

Nystr\"om Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read Diagonal dominance alone cannot guarantee diminishing returns for Nyström error; a 3×3 matrix already breaks it.

desk verdict 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. read the letter →

arxiv 2607.19282 v1 pith:VKSU346N submitted 2026-07-21 math.NA cs.NA

Matthew J. Colbrook This is my paper · ORCID

classification math.NAcs.NA MSC 65F5515B4805C22

keywords NyströmapproximationnuclearnormcolumnsubsetselectionsupermodularitysymmetricdiagonallydominantM-matrixsignedgraphgreedy

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 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.

What carries the argument

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.

What would settle it

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).

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

The 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.

Two 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.

The 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.

Referee Report

0 major / 4 minor

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.

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.

minor comments (4)

[Section 6] 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.
[Theorem 4.2] 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.
[AI declaration] 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 5, Corollary 5.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; counterexamples are self-contained exact constructions.

full rationale

The paper's central claim is a new SDD counterexample to inequality (1.5). It is derived by direct Schur-complement reduction, explicit principal-inverse trace computations (Eqs. 4.2–4.5), and a concrete strictly SDD example (Prop. 4.3). The parameter interval in Theorem 4.2 is obtained by factoring an exact rational expression (4.5) and locating the roots of two quadratics; no fitted parameter is renamed as a prediction, and no curve is normalized to force the sign of ΔE. The M-matrix (SDDM) positive result is explicitly attributed to prior work (Friedland-Gaubert, Atamtürk–Gómez, Chen–Wei, Mahalanabis–Štefankovič, Clark et al.) and is used only as the baseline to contrast with the new SDD obstruction, not as a load-bearing input to the counterexample. The author has no overlapping self-citations used to justify the argument; the Simons workshop report [1] is cited for the statement of Problem 4.6, not as a mathematical premise. The dimension-minimality arguments (Prop. 5.3, Section 5) are elementary 2×2 calculations independent of any cited result, and the nonempty-base embedding via L4 is checked numerically by hand. The only interpretive qualification is that 'diminishing returns' is equated with the exact inequality (1.5), but this is an explicit convention stated in Section 1 and does not make the derivation circular. The robustness remark is mildly overbroad for the boundary example L(t), but since a strictly SDD example with negative ΔE is given separately, this does not create circularity. The derivation chain is self-contained against standard linear algebra, so the score is 0.

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

Only standard matrix analysis and the stated SDD setting are assumed; the construction parameters (e.g., t) are exact variables, not fitted values, and no new entities are introduced.

assumptions (4)

standard math Standard Schur complement and block inverse formulas
Used to prove Theorem 2.1 and Lemma 2.2; standard results in matrix analysis.
standard math Neumann series and Cauchy interlacing for Stieltjes matrices
Used in Theorem 3.1 to expand inverse traces as nonnegative closed-walk sums.
standard math Positive definiteness of principal submatrices and Schur complements
Used throughout to justify trace equals nuclear norm and positivity of quantities.
domain assumption L is SDD and positive definite, M=L+γI, γ>0
Framing of Problem 4.6; the paper answers within this class.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nystr\"om Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction." pith.science (2026). https://pith.science/paper/VKSU346N

@misc{pith2026260719282,
  author       = {Pith},
  title        = {Pith review of: Nystr\"om Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VKSU346N}},
  note         = {Machine review of arXiv:2607.19282}
}

abstract

We study the nuclear-norm error of a column-selected Nystr\"om approximation to $K=(L+\gamma I)^{-1}$, where $L$ is symmetric diagonally dominant and $\gamma>0$. Our central question is whether this error has diminishing returns. A Schur-complement identity reduces the question to traces of inverses of principal submatrices. Existing $M$-matrix results settle the case in which $L$ is a symmetric diagonally dominant $M$-matrix (SDDM). However, diagonal dominance alone is not enough: failure occurs already in dimension three. We construct an exact one-parameter SDD family and determine its sharp failure interval. A $2\times2$ identity proves that dimension three is minimal within the SDD class. We then show that failure persists under strict diagonal dominance; with a nonempty selected base set, dimension four is minimal. Finally, we prove invariance under signature switching, derive a three-dimensional formula showing how a signed triangle causes failure, and give an example in which greedy column selection misses the optimal pair. Together, these findings complete the answer to Problem 4.6 in a recent Simons workshop report.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 3 linked inside Pith

[1]

Amsel, Y

N. Amsel, Y. Baumann, P. Beckman, P. B ¨urgisser, C. Cama ˜no, T. Chen, E. Chow, A. Damle, M. Derezinski, M. Embree, E. N. Epperly, R. F algout, M. Fornace, A. Greenbaum, C. Greif, D. Halikias, Z. Huang, E. Jarlebring, Y. Koutis, D. Kress- ner, R. Kyng, J. Liesen, J. Lok, R. A. Meyer, Y. Nakatsukasa, K. Pearce, R. Peng, D. Persson, E. Rebrova, R. Schneide...

arXiv 2026
[2]

Atamt¨urk and A

A. Atamt¨urk and A. G ´omez,Strong formulations for quadratic optimization with M -matrices and indicator variables, Math. Program., 170 (2018), pp. 141–176

2018
[3]

Berman and R

A. Berman and R. J. Plemmons,Nonnegative Matrices in the Mathematical Sciences, vol. 9 of Classics in Applied Mathematics, SIAM, Philadelphia, 1994

1994
[4]

L. F. O. Chamon, G. J. Pappas, and A. Ribeiro,Approximate supermodularity of Kalman filter sensor selection, IEEE Trans. Automat. Control, 66 (2021), pp. 49–63

2021
[5]

Chen and D

P.-Y. Chen and D. Wei,On the supermodularity of active graph-based semi-supervised learning with Stieltjes matrix regularization, in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 2801–2805. NYSTR ¨OM ERROR BEYONDM-MATRICES11

2018
[6]

Clark, L

A. Clark, L. Bushnell, and R. Poovendran,A supermodular optimization framework for leader selection under link noise in linear multi-agent systems, IEEE Trans. Automat. Control, 59 (2014), pp. 283–296

2014
[7]

Fornace and M

M. Fornace and M. Lindsey,Column and row subset selection using nuclear scores: algorithms and theory for Nystr¨ om approximation, CUR decomposition, and graph Laplacian reduction. arXiv preprint, 2024, https://arxiv.org/abs/2407.01698v2

arXiv 2024
[8]

Fornace and M

M. Fornace and M. Lindsey,An approximation theory for Markov chain compression. arXiv preprint, 2025, https://arxiv.org/abs/2506.22918v3

arXiv 2025

Show all 12 references

[9]

Friedland and S

S. Friedland and S. Gaubert,Submodular spectral functions of principal submatrices of a Hermitian matrix, extensions and applications, Linear Algebra Appl., 438 (2013), pp. 3872– 3884

2013
[10]

Mahalanabis and D

S. Mahalanabis and D. ˇStefankoviˇc,Subset selection for Gaussian Markov random fields. arXiv preprint, 2012, https://arxiv.org/abs/1209.5991

2012 arXiv
[11]

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher,An analysis of approximations for maximizing submodular set functions—I, Math. Program., 14 (1978), pp. 265–294. [12]T. Zaslavsky,Signed graphs, Discrete Appl. Math., 4 (1982), pp. 47–74

1978
[13]

Zaslavsky,Negative (and positive) circles in signed graphs: A problem collection, AKCE Int

T. Zaslavsky,Negative (and positive) circles in signed graphs: A problem collection, AKCE Int. J. Graphs Comb., 15 (2018), pp. 31–48

2018

Pith tools

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

[1] [1]

Amsel, Y

N. Amsel, Y. Baumann, P. Beckman, P. B ¨urgisser, C. Cama ˜no, T. Chen, E. Chow, A. Damle, M. Derezinski, M. Embree, E. N. Epperly, R. F algout, M. Fornace, A. Greenbaum, C. Greif, D. Halikias, Z. Huang, E. Jarlebring, Y. Koutis, D. Kress- ner, R. Kyng, J. Liesen, J. Lok, R. A. Meyer, Y. Nakatsukasa, K. Pearce, R. Peng, D. Persson, E. Rebrova, R. Schneide...

arXiv 2026

[2] [2]

Atamt¨urk and A

A. Atamt¨urk and A. G ´omez,Strong formulations for quadratic optimization with M -matrices and indicator variables, Math. Program., 170 (2018), pp. 141–176

2018

[3] [3]

Berman and R

A. Berman and R. J. Plemmons,Nonnegative Matrices in the Mathematical Sciences, vol. 9 of Classics in Applied Mathematics, SIAM, Philadelphia, 1994

1994

[4] [4]

L. F. O. Chamon, G. J. Pappas, and A. Ribeiro,Approximate supermodularity of Kalman filter sensor selection, IEEE Trans. Automat. Control, 66 (2021), pp. 49–63

2021

[5] [5]

Chen and D

P.-Y. Chen and D. Wei,On the supermodularity of active graph-based semi-supervised learning with Stieltjes matrix regularization, in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 2801–2805. NYSTR ¨OM ERROR BEYONDM-MATRICES11

2018

[6] [6]

Clark, L

A. Clark, L. Bushnell, and R. Poovendran,A supermodular optimization framework for leader selection under link noise in linear multi-agent systems, IEEE Trans. Automat. Control, 59 (2014), pp. 283–296

2014

[7] [7]

Fornace and M

M. Fornace and M. Lindsey,Column and row subset selection using nuclear scores: algorithms and theory for Nystr¨ om approximation, CUR decomposition, and graph Laplacian reduction. arXiv preprint, 2024, https://arxiv.org/abs/2407.01698v2

arXiv 2024

[8] [8]

Fornace and M

M. Fornace and M. Lindsey,An approximation theory for Markov chain compression. arXiv preprint, 2025, https://arxiv.org/abs/2506.22918v3

arXiv 2025