Sublinear Time Eigenvector Approximation via Column Sampling

What the math gives to ML

The paper gives a constructive route to recover outlying eigenspaces of a large bounded symmetric matrix from only a small uniformly sampled set of columns, with the approximation living in the span of those columns. The transferable asset is not merely low-rank approximation, but an explicit spectral criterion: components with eigenvalue magnitude at least \(\epsilon n\) can be approximated with residual \(O(\epsilon n)\) using only \(\tilde O(\log n/\epsilon^4)\) columns. In neural networks, this suggests replacing dense symmetric token-mixing or kernel operations by a landmark-column spectral module, with the sampling budget selected from the desired residual tolerance and the retained rank selected by the outlier threshold.