Did you know that a kernel model can compare every training example with every other one, creating a matrix so large that storing it becomes the problem? The Nyström method reduces that burden by selecting a smaller set of training examples as landmarks, comparing all examples with those landmarks, and reconstructing an approximate kernel matrix from a small central block.
The essential calculation is K̂=C W† Cᵀ. Here C contains kernel similarities between every training point and the selected landmarks, W contains similarities among the landmarks, and W† is the Moore–Penrose pseudoinverse. The hat means approximation; it is not permission to pretend the full matrix was computed exactly. A useful implementation checks landmark coverage, matrix rank, numerical stability, prediction accuracy and memory rather than assuming a small matrix is automatically good.
This article shows where the method comes from, when an approximation is exact, why one RBF example fails badly with too few landmarks, how to build explicit features for ordinary linear learners, and which computational costs are genuinely reduced. The hand-worked examples use constructed numbers, not alleged results from a trained model. All source links lead to original research or official implementation documentation.
The method is useful in machine learning because kernels express nonlinear similarity without requiring every input to be transformed into a named collection of new features. Its limitation is just as important: once only a few landmark directions are retained, distinctions absent from those directions cannot be recreated by an elegant pseudoinverse. The numerical repair is a combination of better sampling, more landmarks, suitable regularisation and evaluation on fresh data.
Contents and reading routes
For a first explanation, read what a kernel represents, landmarks, the matrix shapes, the exact three-point example and the failed Gaussian example. Those chapters provide the core mechanism without requiring an advanced implementation.
For engineering and evaluation, continue through explicit features, pseudoinverse stability, resource accounting, landmark selection, error metrics, downstream learning, numerical checks and deployment controls.
For independent practice, use the changed-kernel transfer problem, the selection workflow, method limits, FAQs and original sources. Every local link on this page points to a unique heading rather than a guessed destination.
What a kernel matrix represents
A kernel k(x,z) is a similarity-like function that, when valid as a positive-semidefinite kernel, can be interpreted as an inner product between possibly implicit features. A kernel matrix K for n observations has entry Kij=k(xi,xj). Its rows are not merely labels: they encode how one observation relates to each of the n observations in the chosen training set. The function and its parameters determine what those relationships mean.
Consider a feature vector holding two measurements from a sensor. A linear kernel uses the dot product of vectors, while a Gaussian radial basis function uses exp(−γ times squared Euclidean distance). The first preserves a linear geometry; the second makes nearby points similar in a way that decays with distance. Neither choice is intrinsically correct. Input scaling and the reader’s scientific question are part of the definition.
If n=20,000, the full square matrix contains 20,000×20,000=400,000,000 entries. As raw 64-bit floating-point values that is 3,200,000,000 bytes, or 3.2 decimal gigabytes, before a factorisation, temporary arrays, data, indexes or additional precision requirements. Computing each pair can also be costly. A small model may fit the data vectors comfortably yet exhaust memory when asked to form their complete Gram matrix.
An exact kernel matrix is often worth paying for on a modest dataset. It gives the learner all similarities implied by the selected kernel, subject to finite-precision arithmetic. The Nyström question arises when storage or optimisation cost is too high. The task is to keep enough geometry for accurate predictions while avoiding most of the quadratic matrix, not to abandon the meaning of the kernel.
Landmarks are training observations, not arbitrary magic points
Choose m landmark examples from the training set, with m much smaller than n. The simplest selection is a uniform random subset without replacement. A landmark can be a typical point in a dense group, a point close to a rare but consequential condition, or an extreme case. Which ones are selected determines the directions represented by the approximation; data coverage is therefore an explicit modelling decision.
The n-by-m matrix C records the kernel between each example and each landmark. The m-by-m matrix W records similarities among landmarks. Instead of computing every one of n² pairs, the system evaluates roughly nm cross-pairs and m² landmark pairs, remembering that a symmetric implementation may avoid repeated pair evaluations. Kernel evaluation cost can still dominate when inputs are high-dimensional or similarities are expensive.
A landmark is not the same as a cluster centroid unless a method deliberately constructs centroids and supports evaluating the kernel on them. Standard subset Nyström uses actual selected observations. If a training group contains many near-identical examples, a uniform sample may choose several redundant landmarks. Conversely a tiny minority pattern may receive none. Those risks cannot be diagnosed solely from the final average validation score.
Select landmarks using training data only. Choosing them with information from a held-out test set contaminates the evaluation even if the labels remain unseen. In a time-series application, future examples can reveal future geometry. In an education application, students from the same family or cohort can leak similar records across splits. Decide the split and deployment constraints before sampling landmarks.
Read the shapes before multiplying any matrices
Let n denote the number of training examples and m the number of landmarks. The full K has dimensions n×n, C has dimensions n×m, and W has dimensions m×m. If W is invertible, C W⁻¹ Cᵀ has shape (n×m)(m×m)(m×n)=n×n. That is the matrix the method approximates, even though a careful implementation need not materialise the final n×n product.
One convenient way to understand the formula is to reorder the observations so the selected landmarks come first. The top-left block of K is W, and the entire first m columns form C. The algorithm uses the observed landmark columns to infer the remaining bottom-right block. It reproduces selected landmark relationships in favourable algebraic conditions, but it can miss variation that does not appear in the selected column span.
The superscript dagger on W is a pseudoinverse, not an ordinary inverse with a more impressive symbol. If W has zero eigenvalues, an inverse does not exist, but a pseudoinverse can act on the nonzero eigenspace. In floating-point software, very small eigenvalues require a practical threshold. That threshold changes the effective rank of the approximation and should be treated as a tunable numerical policy rather than invisible housekeeping.
Do not confuse n, m and input dimension d. A dataset can contain n=20,000 examples, m=200 selected landmarks and d=1,000 input features. The Nyström feature dimension is governed by m or a smaller retained rank, not necessarily by d. The cost of evaluating k(x,z) may still depend on d, so quoting only the sizes of C and W never proves the total system will run quickly.
A worked exact case: three examples and two landmarks
Use the constructed scalar observations x=0, x=1 and x=2 and the valid kernel k(x,z)=1+xz. This corresponds to the two-dimensional explicit feature vector [1,x]. The full Gram matrix has rows [1,1,1], [1,2,3] and [1,3,5]. Although K is 3×3, its rank is at most two because every feature vector has only two coordinates.
Choose x=0 and x=2 as landmarks. Their W is [[1,1],[1,5]]. Its determinant is 5−1=4, so W⁻¹=(1/4)[[5,−1],[−1,1]]. The cross-kernel C has rows [1,1], [1,3] and [1,5]. Every number comes from evaluating 1+xz; no statistical training or numerical library is needed to check the construction.
To reconstruct the middle point’s self-similarity, take its landmark row v=[1,3]. Multiplying W⁻¹v gives [(5−3)/4,(−1+3)/4]=[0.5,0.5]. Then v times that result equals 1×0.5+3×0.5=2. The true k(1,1)=1+1×1=2. In fact C W⁻¹ Cᵀ recovers the whole K exactly for this example.
Why did this work? The two selected landmark feature vectors span the two-dimensional feature space generated by the kernel on these observations. Exact reconstruction here does not mean any two landmarks recover any kernel. A Gaussian RBF kernel evaluated on distinct observations can have much higher effective rank. The mathematical reason to trust the result is a span condition, not the reassuring appearance of a simple matrix.
A deliberately bad approximation that reveals the limitation
Keep x=0,1,2 but change the kernel to k(x,z)=exp(−γ(x−z)²) with γ=ln 2 per squared input unit. Similarity between neighbours one unit apart is exp(−ln 2)=0.5. Similarity between x=0 and x=2 is exp(−4 ln 2)=1/16=0.0625. Every diagonal entry is exactly one because the distance from a point to itself is zero.
Again choose only landmarks x=0 and x=2. Now W=[[1,0.0625],[0.0625,1]]. The middle observation has landmark similarities v=[0.5,0.5]. Because v lies along the symmetric eigenvector of W, its approximated self-similarity is v W⁻¹ vᵀ=0.5/(1+0.0625)=0.4705882353. The true middle diagonal is 1. The absolute deficit is about 0.5294117647.
This calculation is useful precisely because it is unflattering. Two landmarks can encode both endpoints yet fail to reproduce the middle observation’s self-kernel. A downstream learner may still predict adequately if omitted geometry is irrelevant to the label task, but a kernel reconstruction metric would flag the distortion. Neither a small average loss nor a pleasant-looking matrix plot should conceal which input regions are poorly represented.
Adding x=1 as a third landmark makes all three distinct observations landmarks; in exact arithmetic, with a nonsingular W, reconstruction becomes exact on this three-point training matrix. On a real dataset m=n defeats the purpose of a low-rank approximation. The practical problem is choosing enough landmarks to preserve the decision-relevant geometry at a tolerable cost.
Explicit features avoid constructing the large reconstructed matrix
Writing K̂=C W† Cᵀ is a way to explain the approximation, but forming that full product would create an n×n matrix again. Instead diagonalise W=UΛUᵀ, retain stable positive eigenvalues, and construct a feature map B=C U Λ⁻¹ᐟ² on the retained eigenspace. Then B Bᵀ reproduces the chosen Nyström approximation. The large dataset now has one row of m or fewer explicit features per example.
For a new input z, compute similarities to the same training landmarks, obtaining the row c(z), and multiply by the stored normalisation UΛ⁻¹ᐟ². This operation does not require kernel values between z and every old training example. An ordinary linear learner can then use the resulting feature row. Save the landmark points, kernel parameters, normalisation, dtype and preprocessing configuration together as the feature transformer.
The matrix square root is not optional decoration. If one used C directly as the explicit features, their dot products would be C Cᵀ, which generally differs from C W† Cᵀ. The normalisation compensates for similarities and redundancy among landmarks. A reader who replaces W† with the identity without checking W has silently changed the kernel approximation.
Some software descriptions refer to W⁻¹ᐟ² rather than the eigendecomposition. Interpret that notation with care when eigenvalues are near zero. Production code should use a stable decomposition or singular-value treatment and enforce symmetry where appropriate, rather than computing a literal inverse and then taking an unstable matrix square root. Check that every output feature is finite, especially after changes in input scaling.
The pseudoinverse and the meaning of effective rank
Suppose W has eigenvalues 4, 0.5 and 0.0000000001 in dimensionless kernel units. The inverse square-root factors are 0.5, approximately 1.4142 and 100,000 respectively. The third factor can magnify very small numerical differences in an input’s projection. A representation may look higher-dimensional on paper while being extremely sensitive to floating-point perturbations in practice.
A threshold can discard eigenvalues too small relative to the largest reliable scale, producing a lower effective rank r≤m. That decision biases the feature map but may improve numerical stability. The correct threshold depends on the kernel, dataset, precision, and learning objective. Do not copy one tolerance from an unrelated project and call it mathematically optimal.
A duplicate-landmark example makes the issue concrete. If two selected examples have identical features and k(x,x)=1, their 2×2 W is [[1,1],[1,1]], whose eigenvalues are 2 and 0. The determinant is zero, so an inverse does not exist. A pseudoinverse retains the one-dimensional direction and discards the zero direction. Keeping both copies does not magically create two independent features.
The practical diagnostic is to report the eigenvalue spectrum, effective retained rank, and whether rank changes when numerical precision or kernel scale changes. If a model’s feature dimension drops unexpectedly after preprocessing, investigate duplicate or almost-duplicate landmarks, an excessively wide kernel and unintended data scaling before blaming the downstream classifier.
What the computational budget really buys
Return to n=20,000 and m=200. C has 20,000×200=4,000,000 values, occupying 32,000,000 bytes if stored as float64. W has 200×200=40,000 values, about 320,000 bytes. Compare their combined raw storage of approximately 32.32 megabytes with 3.2 gigabytes for full K. Those are decimal byte counts for specified arrays, not total process memory measurements.
Constructing C requires approximately four million kernel evaluations before considering symmetry or caching. Eigen-decomposing W costs on the order of m cubed work in a conventional dense algorithm, and producing B may involve n m² arithmetic. With n=20,000 and m=200, the n m² scaling expression is 800,000,000 multiply-add-scale units; it is a scaling illustration, not a measured count of machine instructions.
The exact baseline must also be specified. Different kernel learners use different algorithms, decomposition strategies and convergence criteria. The 2001 Williams and Seeger analysis describes an attractive O(nm²) regime for its approximation, compared with certain cubic exact operations. It does not promise that every exact kernel model always costs n cubed time or that every Nyström pipeline achieves the theoretical asymptotic speedup on actual hardware.
Peak memory can exceed C plus W because training may materialise B, optimisers store weights and gradients, and kernel computations create temporary batches. Measure memory at the training peak, not just the on-disk feature file. For an especially large dataset, compute transformed features in batches or stream them to a compatible learner, while checking that the same normaliser and landmark identities are used consistently.
Landmark count cannot repair a poorly chosen kernel
Nyström controls which columns of a particular kernel matrix are approximated. It does not choose the underlying notion of similarity for you. For a Gaussian RBF kernel, γ governs the distance scale. If γ is extremely small relative to standardised distances, many points look nearly identical; if it is extremely large, even nearby points can look almost unrelated. Either extreme may create numerical and statistical problems.
Do not tune γ on the test set while congratulating the approximation for generalising. Use training folds or a designated validation split, and select γ jointly with the landmark budget m and downstream regularisation. A model with 500 landmarks and an unsuitable kernel can be less useful than one with 100 landmarks and a well-chosen representation.
Input preprocessing changes kernel values. If one feature represents metres and another represents millimetres, an unscaled Euclidean distance may be dominated by the larger numerical unit. Scaling must be fitted only on training data and then reused for validation and test data. A gamma value that worked with unscaled inputs cannot be assumed to work after standardisation.
For categorical or structured data, the choice of kernel requires its own domain justification. A custom similarity may not be positive semidefinite, in which case the familiar symmetric positive-semidefinite theory no longer applies cleanly. Before invoking pseudoinverse machinery, check symmetry and a few eigenvalues on a manageable representative matrix. A numerical warning may be telling you about an invalid modelling assumption, not merely a library setting.
Uniform, stratified and leverage-aware landmark selection
Uniform sampling without replacement is a transparent baseline. It is easy to reproduce with a documented random seed and does not require label information. Its weakness is that abundant, redundant regions can consume most of the budget. If 95 percent of the training examples lie in one cluster, a 20-landmark random sample could largely ignore rare subgroups, even when those groups carry important decision boundaries.
Stratified sampling can guarantee representation across groups, provided the groups are available at deployment and chosen without peeking at test outcomes. Clustering-based candidates may cover geometric extremes, but computing the clusters has a cost and may depend on scale choices. Leverage-score-inspired schemes seek influential columns, yet estimating good leverage scores itself requires additional algorithms. There is no free universally best subset.
A useful practical comparison fixes the same kernel, downstream learner and evaluation split, then changes only the landmark-selection scheme at a small set of budgets. Repeat random sampling across several seeds to measure variance. Judge success by both prediction quality and subgroup coverage rather than a single average. A favourable one-off random draw should not be presented as an established advantage.
Explain the allocation if labels are used to guide landmark choice. A label-informed sampler is no longer the same unsupervised kernel approximation baseline as one that samples geometry alone. It may be appropriate, but comparison should reflect the extra supervision and prevent labels from leaking from held-out records. Document how often rare or borderline cases become landmarks and whether their inclusion changes decisions.
Choose error metrics that match the reader’s real job
One diagnostic compares the exact and approximate kernel matrices on a manageable sample. The Frobenius difference norm measures entrywise reconstruction error, while a spectral norm is sensitive to the strongest missed direction. Dividing by the corresponding norm of the exact sample matrix creates a relative measure when that denominator is nonzero. State the sample size and selection rule; do not pretend a convenient tiny subsample certifies the whole dataset.
Kernel reconstruction is not the only outcome. A classifier may tolerate some approximation errors but be sensitive to differences near its decision boundary. A regression system may care most about calibrated intervals rather than average training loss. Always assess the actual downstream metric on untouched cases alongside the kernel-level diagnostic. A smaller matrix error is not automatically the best user-facing decision.
For example, suppose an illustrative validation set has 400 cases, and an approximate model gets 360 right. Accuracy is 360/400=90 percent. If a second model gets 364 right, its accuracy is 91 percent, a difference of 4 correct cases out of 400, or one percentage point. This does not prove a meaningful improvement without uncertainty and subgroup analysis; it merely makes the denominator explicit.
If a severe failure is concentrated in 12 unusual observations, an overall 90 percent metric can conceal the application risk. Report meaningful slices with their own denominators, not just a pooled average. A kernel method does not know which errors carry ethical or operational consequences. Human decisions about abstention, review, fairness and risk thresholds remain part of the pipeline.
From Nyström features to an ordinary regularised learner
Suppose B is the n×r Nyström feature matrix and y is a vector of observed targets. One straightforward regression option estimates a linear coefficient vector w by minimising ||Bw−y||²+α||w||² for α≥0. The normal equation is (BᵀB+αI)w=Bᵀy when solved under the usual assumptions. This is ridge regression in approximate kernel features, not a claim that every version of kernel ridge uses identical regularisation conventions.
The feature approach can unlock training algorithms that work naturally with explicit vectors, such as certain linear classifiers or stochastic optimisation procedures. It also changes storage and update patterns: a new example can be mapped through landmarks and processed without comparing it to all n earlier observations. The benefit depends on the learner chosen and whether its loss, calibration and convergence match the task.
Keep target scaling and regularisation separate from kernel approximation quality. If predictions become unstable when α is nearly zero, inspect the spectrum of BᵀB and consider whether the downstream problem is ill-conditioned. Increasing m may add representational capacity but also add correlated directions. More columns do not guarantee a better or more stable final model.
When comparing an explicit Nyström learner with an exact kernel learner, match the objective as closely as practical, while acknowledging implementation differences. Report α under the convention of the actual library, sample weights, intercept handling and loss normalisation. In ridge objectives, including or excluding a factor of 1/n in front of squared error changes the effective interpretation of α; undocumented convention changes make comparisons misleading.
Why this is not the same mechanism as random Fourier features
Random Fourier features and Nyström both convert kernel calculations into smaller explicit representations, but they select those representations differently. A typical random Fourier feature approximation for a shift-invariant kernel samples frequencies from an appropriate spectral distribution. Nyström instead samples or selects landmark observations and uses kernel evaluations against them. The first samples a mathematical feature construction; the second uses geometry observed in training data.
That difference matters after the dataset changes. Nyström features depend on the chosen landmark examples and may require a controlled refit if the training distribution shifts significantly. Random Fourier features also depend on the selected kernel parameters and random draws, but the sampling of frequencies does not usually require knowing the training observations beyond dimensionality. Neither method is automatically more robust to every kind of distribution shift.
A fair comparison fixes the target kernel and downstream learner while varying the explicit feature budget, kernel parameters and random seeds. Record fitting time for the feature transformer separately from transformation and final model training. On a moderate dataset the exact kernel method may still be quick enough to provide a gold-standard baseline, so introducing either approximation could add unnecessary complexity.
Readers can compare the details with eduKate’s already-published Random Fourier Features — Kernel Approximation, Feature Budgets and Honest Validation. That guide owns sampling frequencies and Monte Carlo feature budgets; the present guide owns sampled kernel columns, central-block inversion and the geometry lost when landmarks are insufficient.
Positive semidefiniteness, symmetry and finite precision
For a positive-semidefinite kernel, the true Gram matrix should be symmetric and have nonnegative eigenvalues in exact arithmetic. Small negative eigenvalues in computation may arise from finite precision or a flawed kernel implementation. Large negative eigenvalues can indicate a real invalid-kernel problem. Do not silently repair every negative value and then claim the original similarity function had the required mathematical properties.
Make W numerically symmetric if it is meant to be symmetric and asymmetry is within a justified floating-point tolerance. Use a decomposition designed for symmetric matrices, record how near-zero eigenvalues were handled, and test the transformed features for non-finite entries. The pseudoinverse is useful because singular W is ordinary when selected landmarks are redundant; it is not permission to ignore large condition numbers.
Kernel centring requires special attention. If a training pipeline centres a feature space using training means, applying that centring to held-out observations requires the corresponding training-derived statistics. Centring the entire train-and-test kernel using all samples leaks test information. Explain whether the approximation is made before or after centring and preserve the correct transformation for new inputs.
A validation test should include duplicated examples, near-duplicated landmarks, constant inputs, very distant observations and moderate changes in precision. Compare the result against analytic small matrices like the two examples above. A library can return a number for every case while still being inappropriate for the application’s numerical precision and scientific tolerance.
Independent transfer: add one new feature direction
Try this without using a software library. The original exact toy example used k(x,z)=1+xz at x=0,1,2 and selected x=0 and x=2 as landmarks. Now change the kernel to k(x,z)=1+xz+x²z². With the same two landmarks, does Nyström still exactly reconstruct k(1,1)? Explain your answer by calculating the central W and the middle landmark row before reading the solution.
The new feature map has three coordinates [1,x,x²]. The landmark block becomes W=[[1,1],[1,21]], because k(2,2)=1+4+16=21. Its determinant is 20, so W⁻¹=(1/20)[[21,−1],[−1,1]]. The middle point x=1 has similarities [k(1,0),k(1,2)]=[1,7] to the landmarks.
Compute W⁻¹[1,7]ᵀ=[(21−7)/20,(−1+7)/20]ᵀ=[0.7,0.3]ᵀ. The Nyström approximation to its self-kernel is [1,7]·[0.7,0.3]=0.7+2.1=2.8. The true k(1,1)=1+1+1=3, so the absolute difference is 0.2 kernel units. Two landmarks no longer capture all three feature directions. This is a concrete change-of-context failure, not a mysterious optimiser defect.
The diagnostic lesson is transferable. A method can be exact for one low-rank representation and become approximate after a meaningful change in features or data distribution. Keep the same train/test distinction, check the effective feature rank, and decide whether more landmarks or different selection is warranted. It is not enough to repeat that the earlier two-landmark test passed; the test’s original assumptions have changed.
A defensible sequence for choosing the feature budget
Begin with a small exact baseline if computationally possible. Write down its performance metric, memory footprint and fit time using actual measurements. Next choose several landmark budgets, such as m=50, 100, 200 and 400 if those sizes are feasible for the dataset. Keep kernel parameters and evaluation splits fixed for the first comparison so the effect of landmark count is interpretable.
After this diagnostic, tune the kernel scale and downstream regularisation together with m using training-only cross-validation. Avoid dozens of uncontrolled choices that turn the validation set into a disguised training set. If model selection is extensive, preserve an untouched final test group or apply nested validation where the stakes justify it. Record all candidate configurations including failed ones.
Inspect diminishing returns rather than seeking the highest available m. A jump from 50 to 100 landmarks may sharply improve a rare-class error; a jump from 200 to 400 may double feature storage without meaningfully improving predictions. The desired budget is a decision about utility per unit of computation under constraints, not a moral judgment that more features are always more intelligent.
Finally repeat selected configurations with different landmark draws. Report variability because two random subsets of the same size may cover the dataset differently. If a model only succeeds with a lucky landmark seed, deployment will inherit that fragility. Store the chosen seed and landmark identities for reproducibility, but also treat the seed sensitivity as evidence about whether the method needs more robust selection.
How to deploy the feature map without changing its meaning
An inference service needs the exact preprocessing steps, kernel definition, γ or other parameters, landmark values, normalisation matrix and downstream learner. Store them as one versioned artefact. Loading a new classifier with old landmark normalisation can silently alter the meaning of each feature coordinate. A schema version and a golden set of test examples can detect mismatches before release.
Suppose each incoming example takes a variable-length text representation. The input encoder must produce the same numerical feature schema used to fit the kernel. A change in tokenisation or vectorisation may invalidate the learned distances even when the Nyström transformer itself is unchanged. Test compatibility through the entire encoder–kernel–landmark–predictor path, rather than checking only that the final array has the expected shape.
Latency accounting should include preprocessing, all m similarity evaluations, matrix multiplication and final prediction. A 200-component mapping may be inexpensive for tiny dense vectors and costly for document kernels that use complicated comparisons. Benchmark on realistic batches and hardware. If a timeout occurs, do not return a partially computed feature vector as though it represented the full selected basis.
Distribution shift deserves a maintenance policy. Monitor whether new examples are farther from all stored landmarks or concentrate in areas previously rare in training. Such distances are not, alone, a calibrated out-of-distribution probability. They are screening diagnostics prompting further labelled evaluation and possibly a carefully governed landmark refresh. Never refit landmarks using new test outcomes and still call the previous test untouched.
What the method cannot recover from missing columns
A low-rank kernel approximation cannot manufacture distinctions that its selected landmark directions do not encode. If two kinds of observation look identical against every chosen landmark, the approximate feature map may map them to the same representation even if the full kernel distinguishes them. The resulting prediction errors are representational failures, not necessarily fixable by increasing the number of optimisation epochs.
An approximate positive-semidefinite matrix is also not evidence that the original data labels were correct or that the training sample was representative. Approximation error, sampling bias, label noise, domain drift and unfair outcomes are separate problems. A well-conditioned pseudoinverse can solve a numerical issue while leaving harmful data selection untouched. Diagnose each source with a test targeted to its mechanism.
Nor does the method imply an AI system reasons like a human. It is linear algebra for scalable kernel computations. Large-scale predictors built with it can be useful for classification or regression, but they do not by themselves acquire general intelligence, agency, scientific understanding or reliable causal explanation. Keep claims about capability limited to evaluated tasks and actual evidence.
The practical decision is conditional: use Nyström when a valid kernel model is useful, the full Gram matrix is burdensome, and a carefully chosen landmark basis preserves the information required for decisions at a lower verified cost. Retain an exact small-scale check, a feature-map unit test and an independent validation protocol. Those three checks protect the reader from the most attractive but least justified speedup claims.
Frequently asked questions
Is Nyström the same as selecting a representative training subset?
Not quite. It selects landmark observations but still maps every training example against those landmarks. The n-by-m cross-kernel C therefore uses information from non-landmark examples. Training only on the m landmark labels would be a different data-reduction approach.
Does Nyström require a Gaussian RBF kernel?
No. The underlying theory uses suitable kernels and sampled columns. The official scikit-learn implementation supports several choices, including callable kernels under its documented interface. A valid positive-semidefinite kernel and a clear interpretation of its parameters still matter.
Will doubling landmarks halve prediction error?
There is no universal relationship. Adding landmarks increases the available subspace, but the quality of the selected new columns, kernel spectrum, regularisation and task labels determine benefit. Evaluate budgets on held-out data rather than promising a fixed rate of improvement.
Why use a pseudoinverse instead of adding a little number to the diagonal?
A pseudoinverse handles singular directions by retaining reliable nonzero eigencomponents. Adding a diagonal term changes W and can be a defensible regularisation strategy, but it is not algebraically identical. Document the numerical choice and test its effect.
Can Nyström preserve a small subgroup?
It can, if the selected landmarks and kernel represent that subgroup’s relevant geometry. A random subset can miss a small group, especially with a tight budget. Assess subgroup coverage and predictive errors with explicit denominators instead of relying on overall accuracy.
What is the difference between kernel accuracy and task accuracy?
Kernel accuracy measures how faithfully the approximation reconstructs selected similarities or matrix properties. Task accuracy measures decisions after a particular learner is trained. Either can change without the other changing in a predictable way.
Should I store the approximate full n-by-n matrix?
Usually not when scaling is the goal. Retain a compact feature matrix B and use a compatible downstream learner. Constructing B Bᵀ in full recreates quadratic storage and defeats an important advantage of the feature approach.
Can new observations be transformed without refitting?
Yes, if the kernel and preprocessing are defined for new inputs. Compute their similarities to the stored landmarks and apply the stored normaliser. Refit only under a controlled change-management process, because changed landmarks alter feature coordinates.
Is this method suitable for very small school datasets?
It may be educationally useful, but an exact kernel baseline can be simpler and more transparent when n is small. Approximation adds selection and numerical configuration that need justification. Demonstrate a genuine runtime or memory problem before treating complexity as a benefit.
How can a learner test understanding independently?
Reconstruct the rank-two k(x,z)=1+xz example, then compute the changed-kernel result 2.8 versus 3. Finally explain why the Gaussian middle point’s diagonal drops to about 0.470588 when only endpoints are landmarks. If each failure can be traced to missing feature directions, the mechanism is understood.
Primary research, official documentation and further reading
The explanations and constructed examples above were checked against original kernel-machine research and official open-source documentation. The links identify what the cited sources actually cover; the numerical toy cases are calculations written for this guide rather than benchmark results attributed to those sources.
Williams and Seeger, original Nyström kernel machines paper.
University of Edinburgh primary publication record.
scikit-learn official kernel approximation user guide.
scikit-learn official Nystroem API and parameter documentation.
scikit-learn official comparative RBF approximation example.
Related verified eduKate guides
The How AI Works root guide connects this mechanism with representations, learning objectives, evaluation and responsible use. It is the right route if you need to place kernel approximation within the full AI pipeline.
To compare a different low-dimensional approximation mechanism, use Random Fourier Features — Kernel Approximation, Feature Budgets and Honest Validation. Its sampled spectral features are different from the selected kernel columns explained here.
A practical independent check: write down n, m, the kernel, your selected landmark rows and W’s eigenvalues; calculate one held-out kernel entry by both methods where feasible; and explain the performance metric and computational cost that would justify your chosen approximation.