Nyström Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction

What the math gives to ML

The paper identifies a concrete failure mode for column-selected Nyström approximation: diagonal dominance without the sign restriction of an M-matrix does not guarantee diminishing returns, and a signed three-node interaction is already sufficient. This matters for low-rank attention, kernel transformers, and inducing-point methods, where greedy landmark selection is often assumed to improve monotonically. The transferable asset is a cheap diagnostic and pairwise-lookahead selection rule based on the exact Schur-complement residual, rather than trusting one-step greedy gains. The method is most promising for small or medium landmark budgets, where evaluating a restricted set of candidate pairs is affordable.