What is Nyström Method?
Nyström Method is a low-rank kernel approximation technique that selects landmark samples and reconstructs the full positive-semidefinite Gram matrix from its landmark columns and their intersection matrix.
Quick Facts
| Created | Applied to large-scale kernel approximation by Williams and Seeger in 2000 |
|---|---|
| Specification | Official Specification |
How It Works
Reconstruct the Gram matrix from landmark columns
Selecting landmark indices partitions the kernel matrix into sampled columns C and their intersection W. Using the inverse or pseudoinverse of W yields a positive-semidefinite low-rank reconstruction when the numerical procedure and input kernel satisfy the required conditions.
Williams and Seeger's kernel approximation paper analyzes this construction for large kernel machines. The maximum effective rank is bounded by the number and numerical rank of the landmarks, regardless of the original feature-space dimension.
Choose landmarks and stabilize the retained spectrum
Uniform landmark sampling is simple but can miss rare regions, minority classes, or high-leverage points. Alternatives include stratified, clustering-based, leverage-score, and adaptive selection, each with additional cost and assumptions. Selection must use only information permitted by the training protocol.
Small eigenvalues of W amplify noise in a direct inverse. Use a justified eigentruncation, pseudoinverse tolerance, or regularization, then record landmark identities, ordering, preprocessing, kernel parameters, and factorization settings. Reusing only a random seed may not reproduce the fitted basis.
Validate matrices, features, and downstream decisions
Nyström factors can provide explicit features for training and unseen samples, but inference must evaluate kernels against the same landmarks and apply the same spectral scaling. A new sample outside landmark coverage may receive a confident-looking yet poor representation.
Current scikit-learn Nystroem documentation exposes a reusable feature map. Evaluate relative matrix error, important pairwise similarities, spectral subspace error, task metrics, latency, memory, and performance across landmark seeds against an exact-kernel subset and other approximations.
Key Characteristics
- Approximates a positive-semidefinite kernel matrix from landmark columns
- Produces a rank bounded by the landmark count and retained spectrum
- Uses a data-dependent basis tied to selected training samples
- Trades matrix accuracy and minority coverage against memory and compute
- Supports unseen inputs only through the frozen landmark basis
- Requires stable pseudoinverse, truncation, or regularization of the landmark block
Common Use Cases
- Scaling kernel ridge regression or classification to more samples
- Approximating Kernel PCA and other kernel eigenspaces
- Extending spectral graph embeddings to new observations
- Constructing reusable low-rank features from expensive kernels
- Comparing landmark approximation with exact and Random Fourier baselines
Example
Loading code...Frequently Asked Questions
How does the Nyström Method approximate a kernel matrix?
It selects landmark columns `C`, forms their intersection matrix `W`, and computes `C W_dagger C^T`. The result has rank no greater than the retained landmark spectrum and matches the sampled structure most closely.
How many Nyström landmarks are needed?
There is no universal count. Increase landmarks until matrix, spectrum, and downstream metrics stabilize on representative slices while meeting memory and latency budgets. Repeat landmark selection because a single sample can hide coverage failures.
How should Nyström landmarks be selected?
Uniform sampling is a baseline. Stratification, clustering centers, leverage scores, or adaptive schemes may improve coverage when the data are imbalanced or heterogeneous. Selection must respect train-test boundaries and deployment availability.
How is the Nyström Method different from Random Fourier Features?
Nyström builds a data-dependent basis from sampled kernel columns and can approximate many positive-semidefinite kernels. Classical RFF samples a data-independent spectral map for shift-invariant kernels. Their costs, supported kernels, and failure modes differ.
Can a Nyström feature map transform unseen samples?
Yes. Evaluate the frozen kernel between each new sample and the stored landmarks, then apply the fitted spectral normalization. Do not resample landmarks or refit scaling at inference, and monitor inputs that fall outside landmark coverage.