on improved Nyström bounds

Overview

This post reviews the improved spectral-error analysis for uniform Nyström sampling in Jin, Yang, Mahdavi, Li, and Zhou (Jin et al., 2013). The main point is not that uniform sampling is always optimal. Rather, two structural assumptions—a large eigengap or power-law eigenvalue decay with low eigenvector coherence—allow the classical $O(N/\sqrt{m})$ additive bound to be sharpened to rates that better match observed kernel behavior.

🏷️ Nyström Approximation and Normalization

Let $K\in {\mathbb{R}}^{N\times N}$ be a positive semidefinite kernel matrix with entries $K_{ij}=\kappa (x_i,x_j)$. If $m$ columns are sampled uniformly and $C$ is the corresponding $N\times m$ column block while $W$ is the $m\times m$ intersection block, the standard Nyström approximation is

$$\hat{K}=C{W}^{†}{C}^T.$$

The paper measures the approximation error in spectral norm. The classical benchmark, under a bounded diagonal assumption, is an additive estimate of the form

$$\Vert K-\hat{K}{\Vert }_2\le {\lambda }_{m+1}+O\left(\frac{N}{\sqrt{m}}\right),$$

where ${\lambda }_i$ are the eigenvalues of $K$ in decreasing order. The factor $N$ is not a typo: the analysis works with the empirical integral operator

$$L_{N}f(\cdot )=\frac{1}{N}\sum _{i=1}^N\kappa (x_i,\cdot )f(x_i),$$

whose eigenvalues are ${\lambda }_i/N$. Thus a normalized operator error of order $m^{1-p}$ appears as a matrix spectral error of order $N/m^{p-1}$.

The paper’s first reduction is also important. If the sampled points are ${\hat{x}}_1,\dots ,{\hat{x}}_m$, define

$${\mathcal{H}}_a=\mathrm{span}\{\kappa ({\hat{x}}_1,\cdot ),\dots ,\kappa ({\hat{x}}_m,\cdot )\}$$

and

$${\mathcal{H}}_b=\left\{\sum _{i=1}^N{u}_i\kappa (x_i,\cdot ):\sum _{i=1}^N{u}_i^2\le 1\right\}.$$

With the paper’s squared RKHS-error convention, the Nyström spectral error is exactly the worst projection error

$$\Vert K-\hat{K}{\Vert }_2=\underset{g\in {\mathcal{H}}_b}{\max }\underset{f\in {\mathcal{H}}_a}{\min }\Vert g-f{\Vert }_{{\mathcal{H}}_{\kappa }}^2.$$

This reformulation is the real technical bridge: sampling columns of $K$ is converted into approximating the span of all kernel sections by the span of sampled kernel sections.

🌊 The Large-Eigengap Bound

The first improvement assumes that there is a rank $r$ at which the spectrum drops sharply. Specifically, for some $\rho \in (0,1/2)$,

$${\lambda }_r=\Omega \left(\frac{N}{m^{\rho }}\right),{\lambda }_{r+1}=O\left(\frac{N}{m^{1-\rho }}\right).$$

The concentration argument gives, with high probability,

$$\Vert K-\hat{K}{\Vert }_2\le \frac{16[\log (2/\delta ){]}^2{N}^2}{m{\lambda }_r}+{\lambda }_{r+1}.$$

Under the eigengap hypothesis this simplifies to

$$\Vert K-\hat{K}{\Vert }_2=O\left(\frac{N}{m^{1-\rho }}\right).$$

This improves the $O(N/\sqrt{m})$ term whenever $\rho <1/2$. The assumption is strong, but the interpretation is clean: if the sampled kernel sections resolve the dominant eigenspace and the next eigenvalue is already small, the Nyström error is governed by the post-gap scale rather than by the generic square-root sampling rate.

📉 Power-Law Decay and Coherence

The sharper and more explanatory result assumes power-law spectral decay. Write the eigendecomposition as $K=V\Lambda V^T$ and define the coherence of the eigenvector matrix by

$$\mu =\sqrt{N}\underset{1\le i,j\le N}{\max }|V_{ij}|.$$

Low coherence means that the eigenvectors are not concentrated on a few coordinate directions. This is exactly the condition under which uniform column sampling can see the important spectral directions without leverage-score reweighting.

Assume the normalized eigenvalues follow a $p$-power law:

$$\frac{{\lambda }_i}{N}\asymp i^{-p},p>1.$$

Under the paper’s logarithmic sample-size condition depending on $\mu$, $p$, and $N$, Theorem 9 gives the high-probability estimate

$$\Vert K-\hat{K}{\Vert }_2\le \tilde{O}\left(\frac{N}{m^{p-1}}\right),$$

where $\tilde{O}$ hides polylogarithmic factors in $N$. The gain over $O(N/\sqrt{m})$ becomes substantial when the spectrum is strongly skewed.

The proof mechanism is borrowed from compressive sensing. Sampling rows of $V$ behaves stably on a leading spectral block when $\mu$ is small. If $r$ is chosen on the scale

$$r\approx \frac{m}{{\mu }^2\mathrm{polylog}(N)},$$

then the projection error can be bounded by a multiple of the spectral tail

$$\sum _{i>r}{\lambda }_i.$$

For a $p$-power law,

$$\sum _{i>r}{\lambda }_i\lesssim N{\int }_r^{\infty }{x}^{-p}dx=O\left(N{r}^{1-p}\right),$$

and substituting the admissible $r$ yields the announced $N/m^{p-1}$ rate up to logarithmic and coherence factors.

Assumptions Matter

The power-law result is not a universal Nyström guarantee. The paper also proves lower bounds showing that arbitrary kernel matrices retain a polynomial-in-$m$ obstruction; the improved upper bounds are conditional. Low coherence and spectral decay are doing real work: a flat spectrum, or eigenvectors concentrated on a small set of coordinates, can defeat uniform sampling.

🎯 Consequence for Kernel Classification

The classification section uses the matrix approximation bound as an input to a generalization estimate. If

$$\Gamma (N,m)$$

denotes a high-probability upper bound for $\Vert K-\hat{K}{\Vert }_2$, then the classifier trained through the sampled kernel sections pays an additional error term controlled by $\Gamma (N,m)$.

For $p$-power-law eigenvalues, Theorem 9 gives $\Gamma (N,m)=O(N/m^{p-1})$ up to logarithms. Combining this with the eigenvalue decay estimate for the full kernel classifier yields an excess-risk scale of the form

$$O\left(N^{-p/(p+1)}+m^{-(p-1)/2}\right).$$

Choosing

$$m=N^{2p/(p^2-1)}$$

balances the Nyström error with the full-kernel statistical rate. This gives a classifier with essentially the same asymptotic generalization rate while using sublinear support-vector budget whenever

$$p>1+\sqrt{2}.$$

📊 Summary

Regime	Structural input	Spectral-error bound
Generic additive theory	Bounded diagonal, no spectral structure	${\lambda }_{m+1}+O(N/\sqrt{m})$
Large eigengap	${\lambda }_r=\Omega (N/m^{\rho })$ and ${\lambda }_{r+1}=O(N/m^{1-\rho })$	$O(N/m^{1-\rho })$
Power-law spectrum	${\lambda }_i/N\asymp i^{-p}$ and low coherence	$\tilde{O}(N/m^{p-1})$

📝 Notes

• The old heuristic that $W$ becomes an eigenvalue diagonal in a continuum limit is misleading. $W$ is a sampled intersection matrix; the correct limiting object is the empirical or population integral operator.
• Uniform sampling is justified here by incoherence. Modern ridge-leverage-score sampling can often remove or weaken this assumption, but it changes the sampling distribution and belongs to a different analysis.
• The bound is additive in spectral norm. It should not be read as a relative-error statement of the form $\Vert K-\hat{K}{\Vert }_2\le (1+\epsilon )\Vert K-K_r{\Vert }_2$.

🔗 See Also

• on eigenvalue estimate of kernel --- Eigenvalue decay for integral operators supplies the spectral input that distinguishes the flat-spectrum and power-law regimes.
• on two-layer ReLU networks --- Random-feature and neural-tangent kernels produce finite empirical kernel matrices where Nyström-style spectral approximation is a natural comparison point.
• on Sylvester’s determinantal identity and Schweinsian expansion --- Schur-complement and pseudoinverse identities are the algebraic background for many column-subset approximations, even though this paper’s proof is phrased through RKHS projection.

📚 References

🐻  Jin, R., Yang, T., Mahdavi, M., Li, Y.-F. & Zhou, Z.-H. 2013. Improved Bounds for the Nyström Method With Application to Kernel Classification. IEEE Transactions on Information Theory 59(10), 6939–6949.