A kernel method begins with a beautiful lie:

we can reason in a high-dimensional feature space without writing the features
down

For points \(x_1,\ldots,x_n\), the kernel matrix

\[K_{ij}=k(x_i,x_j)\]

acts as the table of all inner products in that hidden space. Support vector machines, kernel ridge regression, Gaussian processes, spectral clustering, kernel PCA: they all learn by touching this table.

Then \(n\) grows.

The table is \(n\times n\). Storing it is quadratic. Factoring it is often cubic. The elegant feature-space trick becomes a memory bill.

The Nystrom move is wonderfully blunt:

keep some columns

If \(C\) is the matrix of selected columns of \(K\), and \(W\) is the small intersection matrix between those selected rows and columns, approximate

\[K \approx C W^+ C^T.\]

The formula fits on one line. The problem does not.

The problem is witness selection.

Columns Are Witnesses

A column of a kernel matrix is not just a column. It is one training point’s similarity story about every other training point.

Keeping a landmark point says:

this point's relationships are useful enough to represent many other
relationships

If the landmarks span the important directions of the hidden feature matrix, the approximation works. If they miss a narrow cluster, a boundary region, or an isolated high-leverage point, the matrix can look cheap and the downstream prediction can still pay later.

Williams and Seeger helped bring the Nystrom method into kernel machines, showing how a subset of columns can approximate the eigendecomposition of a large Gram matrix and reduce kernel-machine computation.1 Drineas and Mahoney then put the column-sampling question into the language of randomized matrix approximation, emphasizing that the sampling distribution is not an implementation detail.2

That is the right frame:

Nystrom is not a compression format; it is a sampling policy

A Landmark Lab

The lab below builds a synthetic two-dimensional regression problem. It forms the full RBF kernel matrix, fits exact kernel ridge regression, then replaces the full kernel with a Nystrom approximation.

It compares three landmark policies:

  • uniform, a deterministic random-looking subset;
  • farthest-point, a geometric coverage rule in input space;
  • ridge leverage, an oracle diagnostic that keeps points with large diagonal entries of \(K(K+\lambda I)^{-1}\).

The ridge-leverage option is deliberately labeled as a diagnostic. The browser computes it from the full kernel matrix, so it is not a scalable production algorithm. It is there to show what the statistical difficulty of the kernel ridge problem thinks is important.

Deterministic browser experiment. The ridge-leverage option computes diagonal entries of K(K + lambda I)^-1 from the full kernel, so treat it as an oracle diagnostic for this small problem, not a scalable implementation.

The default run keeps 14 columns from a 72 x 72 kernel matrix. The effective dimension, measured as the sum of the ridge leverage scores, is about 33.8. So the default is intentionally under-budgeted.

In the lab audit, the ridge-leverage policy captures more leverage mass than the uniform sample, but its full-matrix Frobenius error can look worse. That is not a bug. It is the lesson.

Uniform landmarks may cover the average kernel matrix well. Ridge-leverage landmarks may focus on points that matter more for kernel ridge regression. Farthest-point landmarks may cover the geometry of input space while ignoring where the target function is hard.

Those are three different currencies:

matrix reconstruction
geometric coverage
statistical prediction

The Nystrom formula does not choose among them. The landmark policy does.

The Matrix Error Is Not The Whole Loss

The heatmap panel shows

\[|K-CW^+C^T|.\]

This is the obvious numerical linear algebra view: how much of the Gram matrix did the landmark columns fail to reconstruct?

It is a useful view. It is not the whole view.

Kernel ridge regression solves

\[\alpha = (K+\lambda I)^{-1}y.\]

The downstream predictor is not equally sensitive to every entry of \(K\). The regularization \(\lambda\) damps some directions. The target vector \(y\) loads some directions more than others. A small-looking matrix error can hurt prediction if it lands in a direction the regression actually uses. A large-looking matrix error can matter less if it lives in a direction the ridge penalty suppresses.

That is why the lab reports both:

  • kernel error, a relative Frobenius error in the Gram matrix;
  • prediction gap, the RMSE between exact KRR predictions and Nystrom KRR predictions;
  • Nystrom RMSE, error against the known latent function.

When those disagree, believe the disagreement. It is telling you which problem you are solving.

Why Leverage Scores Enter

For a positive semidefinite kernel matrix, the ridge leverage score

\[\ell_i(\lambda) = \left[K(K+\lambda I)^{-1}\right]_{ii}\]

measures how much point \(i\) participates in the effective degrees of freedom of kernel ridge regression. Summing these scores gives

\[d_{\mathrm{eff}}(\lambda) = \operatorname{tr}\!\left(K(K+\lambda I)^{-1}\right),\]

which is the effective dimension of the regularized problem.

Bach’s sharp analysis showed that, for kernel ridge regression, the number of columns needed by random subset approximations can be tied to this degrees-of-freedom quantity rather than to a crude ambient dimension.3 El Alaoui and Mahoney extended this statistical view into fast randomized kernel ridge regression guarantees based on approximate ridge leverage scores.4

This is the pleasant version of the story:

sample columns in proportion to the directions the regularized learner can
actually use

The unpleasant version is that computing exact leverage scores already requires too much knowledge of the full matrix. Practical algorithms approximate them, use recursive sampling, use random features, cluster landmarks, mix strategies, or accept a looser guarantee.

The lab is small enough to show the idealized receipt. It is not pretending the receipt is free.

Lengthscale Decides The Witness Problem

Move Lengthscale down.

The RBF kernel becomes local. Each point mostly speaks for nearby points. The kernel matrix approaches a spiky table, and the number of landmarks needed rises. A few columns cannot represent many isolated neighborhoods.

Move Lengthscale up.

The kernel becomes smoother. Many rows of the Gram matrix look similar. A small set of witnesses can speak for more of the table, and the effective dimension falls.

This is a good way to read kernel hyperparameters operationally. A short lengthscale does not only say “the function can wiggle.” It says:

the Gram matrix has more local stories to remember

That memory bill shows up whether you pay it with full kernel methods, landmarks, random Fourier features, inducing points, or sparse Gaussian process approximations.

The Subset Is A Model Choice

It is tempting to treat the landmark subset as an acceleration detail:

same model, faster implementation

Sometimes that is a reasonable approximation. But in a finite budget, the subset changes the model. It changes which neighborhoods can be represented, which eigen-directions survive, which training points can exert influence, and which test points receive sensible similarities.

Gittens and Mahoney’s later review makes this point from the large-scale matrix approximation side: Nystrom methods are part of a family of randomized low-rank approximations, and their behavior depends heavily on coherence, sampling, and the target task.5

For a real system, I would want the Nystrom report to include:

  • the landmark policy, not just the landmark count;
  • a sweep over landmark budgets;
  • the kernel hyperparameters and regularization;
  • matrix approximation error and downstream validation error;
  • leverage-score or coverage diagnostics;
  • stability across seeds;
  • a comparison to random features or a full-kernel run on a smaller sample;
  • the failure case where the landmark budget is too small.

The last item matters. A compression method that never shows where it breaks is not a method. It is a sales page.

Keep The Witnesses Honest

The Nystrom approximation is attractive because it keeps the kernel story interpretable. Unlike a dense random projection, a landmark column is a real example. You can look at it and ask why it was kept.

That is also the danger. A real example feels like evidence. But a chosen example is evidence under a sampling policy. Uniform sampling answers one question. Farthest-point traversal answers another. Ridge leverage answers another. Clustering answers another. Determinantal point processes, recursive sampling, and approximate leverage algorithms answer still others.

The one-line formula is:

\[K \approx C W^+ C^T.\]

The real question is:

which columns get to tell the story?

In kernel methods, every row is a relationship to the whole dataset. Keeping a few rows is an editorial act. The witnesses may be honest, but they are not neutral.

Paper Trail

  1. Christopher K. I. Williams and Matthias Seeger, “Using the Nystrom Method to Speed Up Kernel Machines”, NeurIPS, 2000. ↩

  2. Petros Drineas and Michael W. Mahoney, “On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning”, Journal of Machine Learning Research, 6, 2005, pp. 2153-2175. ↩

  3. Francis Bach, “Sharp Analysis of Low-Rank Kernel Matrix Approximations”, COLT, 2013. Proceedings PDF: PMLR. ↩

  4. Ahmed El Alaoui and Michael W. Mahoney, “Fast Randomized Kernel Ridge Regression with Statistical Guarantees”, NeurIPS, 2015. Author PDF: Berkeley. ↩

  5. Alex Gittens and Michael W. Mahoney, “Revisiting the Nystrom Method for Improved Large-scale Machine Learning”, Journal of Machine Learning Research, 17, 2016. ↩