Nyström method for symmetric indefinite matrices

What the math gives to ML

The paper replaces the usual Nyström core A(I,I)^{\dagger}, which can be unstable for symmetric indefinite matrices, by fitting the core through a two-sided sketched least-squares problem. This is transferable to low-rank neural interaction layers whose pairwise matrix is symmetric but signed or indefinite, such as graph propagation with signed affinities, centered kernel layers, and symmetrized token interactions. The key asset is that the fitted core is not forced to inherit the spectrum of a potentially ill-conditioned landmark submatrix; it is selected to minimize a sketched reconstruction residual and may remain indefinite. A practical first target is a dense symmetric graph or set interaction layer, replacing an n by n matrix-vector product with O(nr) operations while retaining a small r by r core.