Chapter map

1. 1. Kernel matrix
2. 2. Landmark
3. 3. Column block
4. 4. Intersection
5. 5. Approximation
6. 6. PSD check
7. 7. Residual
8. 8. Frobenius error
9. 9. Optimal baseline
10. 10. Gap
11. 11. Other landmark
12. 12. All landmarks
13. 13. Regularization
14. 14. Downstream test
15. 15. Conclusion

Visit the How Mathematics Works hub for the wider series and its connections to education, reasoning, science, computing, design and careers.

---

1. Kernel matrix

This step deserves a careful pause. Set K=[[1,.5],[.5,1]].

A concrete situation

K is symmetric positive definite.

What the mathematics does not license

Check eigenvalues. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record K. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

2. Landmark

The useful question is not only how to calculate, but what the calculation assumes. Choose index one.

A concrete situation

One of two items is sampled.

What the mathematics does not license

State rule. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record landmark. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

3. Column block

A small example makes the mechanism visible. Form C=[[1],[.5]].

A concrete situation

C is 2 by 1.

What the mathematics does not license

Keep both relationships. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record C. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

4. Intersection

This is where modelling choices begin to affect evidence. Set W=[[1]].

A concrete situation

W is invertible.

What the mathematics does not license

Use pseudoinverse generally. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record W. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

5. Approximation

The central mathematical idea is concrete. Compute C W+ C transpose.

A concrete situation

Ktilde=[[1,.5],[.5,.25]].

What the mathematics does not license

Check dimensions. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record Ktilde. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

6. PSD check

Here the geometry becomes operational. Find eigenvalues or factor form.

A concrete situation

Ktilde is PSD and rank one.

What the mathematics does not license

Factor form proves PSD. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record result. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

7. Residual

This step deserves a careful pause. Subtract from K.

A concrete situation

Residual=[[0,0],[0,.75]].

What the mathematics does not license

Keep sign. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record residual. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

8. Frobenius error

The useful question is not only how to calculate, but what the calculation assumes. Take the Frobenius norm.

A concrete situation

The error is .75.

What the mathematics does not license

Square, sum, root. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record .75. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

9. Optimal baseline

A small example makes the mechanism visible. Use eigenvalues 1.5 and .5.

A concrete situation

Best rank-one error is .5.

What the mathematics does not license

Use the same norm. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record baseline. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

10. Gap

This is where modelling choices begin to affect evidence. Compare .75 with .5.

A concrete situation

The landmark constraint costs .25 here.

What the mathematics does not license

Do not call Nyström optimal. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record gap. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

11. Other landmark

The central mathematical idea is concrete. Choose index two.

A concrete situation

Symmetry gives the same error.

What the mathematics does not license

Explain symmetry. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record result. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

12. All landmarks

Here the geometry becomes operational. Choose both indices.

A concrete situation

Exact recovery returns K.

What the mathematics does not license

Cost rises. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record tradeoff. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

13. Regularization

This step deserves a careful pause. Replace W+ by a regularized inverse if justified.

A concrete situation

Bias and stability change.

What the mathematics does not license

State parameter. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record method. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

14. Downstream test

The useful question is not only how to calculate, but what the calculation assumes. Fit the eligible kernel model.

A concrete situation

Matrix error and prediction error differ.

What the mathematics does not license

Validate separately. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record evidence. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

15. Conclusion

A small example makes the mechanism visible. State kernel, landmarks, inverse rule and errors.

A concrete situation

The worked error is .75 versus .5 optimum.

What the mathematics does not license

Keep scope precise. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Write conclusion. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

A seven-day practice lab

1. Day 1: define the decision, observation unit, X variables and Y or reference condition.
2. Day 2: reproduce the smallest worked example and check every dimension, unit and sign.
3. Day 3: build a transparent baseline and write what it assumes.
4. Day 4: fit the main method inside a training-only pipeline; record every parameter.
5. Day 5: challenge one assumption with a deliberately difficult dataset or operating regime.
6. Day 6: compare validation metrics with the practical workload created by errors.
7. Day 7: present one supported conclusion, one unresolved uncertainty and one safe next experiment.

Questions for a student, parent or mentor

• Which part of the model is a mathematical definition, and which part is a choice?
• What small calculation would catch a sign, scale or dimension error?
• What evidence comes from training, validation and the untouched test?
• What benign condition could look like a fault or prediction failure?
• How would the answer change for another response, asset, school project or time period?
• What should a human review before acting on the score?

A method-specific audit before deployment

The Nyström method approximates a large positive semidefinite kernel or Gram matrix using a smaller set of landmark rows and columns. If C contains the columns associated with the landmarks and W is their intersection block, a common approximation is Ktilde=C W+ C transpose, where W+ is the Moore–Penrose pseudoinverse.

Take K=[[1,0.5],[0.5,1]] and choose the first item as the only landmark. Then C=[[1],[0.5]], W=[[1]], and Ktilde=[[1,0.5],[0.5,0.25]]. The approximation is positive semidefinite and has rank one.

The residual is K-Ktilde=[[0,0],[0,0.75]], so its Frobenius norm is 0.75. The eigenvalues of K are 1.5 and 0.5, making the best rank-one Frobenius error 0.5. This one-landmark Nyström approximation is useful but not optimal.

Landmark choice matters because a landmark must represent relationships across the dataset. Uniform sampling is simple; leverage scores, clustering or determinantal ideas can be more data-aware. Each choice changes computation, randomness and the theorem that applies.

The kernel matrix must be built from a stated kernel and its parameters. A Gaussian radial-basis kernel, for example, depends on a bandwidth. Changing that bandwidth can change the spectrum and which landmarks are informative before Nyström approximation begins.

Positive semidefiniteness is central to the usual Gram-matrix story. Numerical rounding, an indefinite similarity function or inconsistent preprocessing can violate it. Check symmetry and eigenvalues within a declared numerical tolerance instead of assuming every similarity matrix is a valid kernel.

If W is singular or nearly singular, the pseudoinverse tolerance or regularization affects the approximation. Regularization may improve stability, but it creates a different estimator. The value and purpose of the regularizer should be reported.

Did You Know? Nyström approximation can be seen as extending information from a small landmark system to all observations. The extension is mathematical interpolation in a kernel geometry, not evidence that the landmarks are socially or causally representative.

In kernel machines and Gaussian-process calculations, the attraction is computational: a low-rank factor can replace operations on the full dense matrix. The actual cost depends on the number of landmarks, kernel evaluation, memory layout and solver, so a complexity statement needs its assumptions.

Students should separate three errors: the original modelling error of the kernel, the low-rank approximation error, and the downstream prediction or inference error. A small matrix residual can support the second claim without proving the first or third.

A useful classroom experiment fixes K and tests each possible single landmark. Compute C, W, Ktilde and the residual. Then enlarge the landmark set and observe that exact recovery is possible when all necessary directions are captured.

The best rank-k SVD benchmark answers how well any rank-k matrix could approximate K in the selected norm. Nyström is more constrained because its factors are tied to sampled columns. The gap between the two measures the cost of that constraint for the realised landmarks.

For AI and statistics, a faster kernel approximation may make a method feasible at larger scale. It does not make the learned system unbiased, explainable or accurate on new populations. Sampling design, validation and domain review remain necessary.

For parents and students, landmarks offer a clear analogy: a few examples can help organise a large topic when they genuinely cover its structure. Choosing only familiar examples may leave an important direction unseen.

A responsible report names the kernel, parameters, matrix size, landmark rule, landmark count, pseudoinverse or regularization convention, random seed policy, residual norm, spectral baseline and downstream validation plan.

The approximation may also be written through a low-rank feature factor. If W=V Lambda V transpose on its positive numerical subspace, one can form C V Lambda^{-1/2}; multiplying that factor by its transpose returns the Nyström matrix. This form makes positive semidefiniteness and storage requirements easier to inspect.

Approximation quality can be measured in spectral, Frobenius or trace-related terms, and those errors answer different questions. A small Frobenius error can coexist with a concerning worst-direction error. The norm must be named, and the best-rank comparison must use the same norm and the same matrix.

When landmarks come from clustered data, a simple random sample may overrepresent the largest cluster. Stratified or adaptive choices can improve coverage but change the probability model. If labels or protected attributes guide selection, document the governance reason and evaluate whether the procedure introduces leakage or unfair treatment.

A diagonal correction is sometimes used when an approximation understates self-similarity. Such a correction can improve a chosen diagnostic but no longer equals the basic C W+ C transpose construction. Name the variant and recalculate both PSD behaviour and the downstream objective.

Out-of-sample use requires a rule for computing kernels between new points and the saved landmarks. The same preprocessing and kernel parameters must be used. If those values drift, the stored low-rank factor and the new evaluations no longer represent one coherent geometry.

---

Frequently asked questions

What does the Nyström method approximate?

Usually a positive semidefinite kernel or Gram matrix.

What are landmarks?

The sampled indices defining C and the smaller intersection block W.

Why use a pseudoinverse?

W may be singular or rank deficient.

Is the result the best rank-k approximation?

Not necessarily; landmark constraints can create a gap.

Does a small kernel residual prove prediction accuracy?

No. Downstream validation is separate.

What must be reported?

Kernel, parameters, landmark rule and count, inverse convention, residual, baseline and validation.

---

Primary source and fact-check note

Christopher K. I. Williams and Matthias Seeger, “Using the Nyström Method to Speed Up Kernel Machines,” NeurIPS 13, 2001. Definitions and core claims in this article were checked against this primary publication. Calculations shown here were independently recomputed. Examples are educational illustrations; they are not reported industrial performance results.

Useful next reading

• Randomized SVD
• CUR matrix source
• Eckart–Young–Mirsky theorem
• How Mathematics Works
• Study and learning methods

Keep the options open. Mathematics education supports clearer questions, transferable problem-solving skills and informed choices across science, engineering, computing, AI, statistics, design and many other careers. It does not guarantee intelligence, income, admission or employment; those outcomes depend on far more than one subject or model.

Matrix audit: geometry, sampling and approximation logic

Kernel audit

Verify symmetry and positive semidefiniteness.

Landmark audit

Record rule, count and realised indices.

Inverse audit

State pseudoinverse tolerance or regularization.

Validation audit

Separate matrix residual from downstream performance.

Mechanism workshop: calculate, challenge and transfer

Manual reconstruction

Build the smallest exact example for kernel landmarks. Label shapes, ranks, norms and assumptions.

Assumption map

Place PSD, rank, sampling, rescaling and probability conditions beside the step they permit.

Counterexample

Choose a poor row, column, landmark or sketch and identify the first failed conclusion.

Sensitivity

Change one sample, probability, kernel parameter or sketch size while holding the rest fixed.

Independent verification

Recompute products, scores, eigenvalues and residuals through a second route.

Simulation

Repeat the randomized procedure and plot realised error without turning frequency into certainty.

Engineering transfer

Map the mechanism to compression, kernels, regression or scientific computing.

AI transfer

Explain a learning use while separating speed, accuracy, privacy and fairness.

Parent explanation

Describe coverage and representative examples in clear language without guaranteed results.

Limit statement

Write one supported claim, one overclaim and one repaired conclusion.

Evidence notebook: reconstruct every step

Evidence notebook 1: Kernel matrix

Step 1 isolates kernel matrix. Set K=[[1,.5],[.5,1]]. The checked result is: K is symmetric positive definite. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Check eigenvalues. Record K. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 2: Landmark

Step 2 isolates landmark. Choose index one. The checked result is: One of two items is sampled. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: State rule. Record landmark. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 3: Column block

Step 3 isolates column block. Form C=[[1],[.5]]. The checked result is: C is 2 by 1. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Keep both relationships. Record C. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 4: Intersection

Step 4 isolates intersection. Set W=[[1]]. The checked result is: W is invertible. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Use pseudoinverse generally. Record W. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 5: Approximation

Step 5 isolates approximation. Compute C W+ C transpose. The checked result is: Ktilde=[[1,.5],[.5,.25]]. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Check dimensions. Record Ktilde. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 6: PSD check

Step 6 isolates psd check. Find eigenvalues or factor form. The checked result is: Ktilde is PSD and rank one. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Factor form proves PSD. Record result. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 7: Residual

Step 7 isolates residual. Subtract from K. The checked result is: Residual=[[0,0],[0,.75]]. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Keep sign. Record residual. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 8: Frobenius error

Step 8 isolates frobenius error. Take the Frobenius norm. The checked result is: The error is .75. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Square, sum, root. Record .75. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 9: Optimal baseline

Step 9 isolates optimal baseline. Use eigenvalues 1.5 and .5. The checked result is: Best rank-one error is .5. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Use the same norm. Record baseline. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 10: Gap

Step 10 isolates gap. Compare .75 with .5. The checked result is: The landmark constraint costs .25 here. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Do not call Nyström optimal. Record gap. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 11: Other landmark

Step 11 isolates other landmark. Choose index two. The checked result is: Symmetry gives the same error. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Explain symmetry. Record result. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 12: All landmarks

Step 12 isolates all landmarks. Choose both indices. The checked result is: Exact recovery returns K. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Cost rises. Record tradeoff. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 13: Regularization

Step 13 isolates regularization. Replace W+ by a regularized inverse if justified. The checked result is: Bias and stability change. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: State parameter. Record method. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 14: Downstream test

Step 14 isolates downstream test. Fit the eligible kernel model. The checked result is: Matrix error and prediction error differ. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Validate separately. Record evidence. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 15: Conclusion

Step 15 isolates conclusion. State kernel, landmarks, inverse rule and errors. The checked result is: The worked error is .75 versus .5 optimum. Preserve shapes, rank, sampling rule, probabilities, kernel parameters, sketch definition and units beside every number. The safeguard is: Keep scope precise. Write conclusion. Change one input while holding the others fixed, recalculate the product, score, approximation or full residual, and explain whether the change comes from subspace coverage, conditioning, landmark choice, rescaling, randomness or rounding. Ask a second reader to reproduce the arithmetic. Finish with the narrow conclusion and the evidence still missing.

Failure cases and responsible recovery

Invalid kernel

A similarity matrix need not be PSD. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Landmark shortcut

A small landmark set can miss directions. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Inverse omission

Singular W needs a declared convention. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Optimality claim

Nyström need not equal the best rank-k matrix. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Parameter silence

Kernel bandwidth changes the geometry. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Residual conflation

Matrix error is not prediction error. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Cost shortcut

Runtime depends on landmarks and implementation. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.

Representation claim

Landmarks need domain coverage checks. Build a small counterexample, select an eligible theorem and state the missing evidence before calculating again.