Why are some landmarks more informative?
A landmark retains one feature direction. If all landmarks lie along a single direction, repeating that direction cannot recover a second one, however large the selected diagonal entries look. We need a sampling rule that measures a column after the correlations among columns have been taken into account. A ridge leverage score does this at a chosen scale. A direction much smaller than that scale receives less attention; a direction much larger than it is counted almost once.
The guarantee here concerns one fixed finite positive semidefinite (PSD) Gram matrix. It is deliberately elementary: a second-moment calculation and Markov's inequality replace a sharper matrix concentration theorem. The resulting landmark budget can be conservative. It nevertheless shows exactly why the effective dimension, a regularization scale and a nonzero chance of missing directions appear in the statement.
Scores and independent draws
Definition 16.1.1
(Ridge leverage scores and effective dimension)
Let be symmetric PSD and let . Define
The number is the ridge leverage score of index at scale , and is the effective dimension.
If , then . Hence , , and . Thus : it counts each eigenvector fractionally, according to the chosen scale. It is generally not an integer.
Concept lensAnalytic
A leverage score as a regularized reconstruction cost
With , each score is the optimal value of a small ridge problem:
Setting the gradient to zero gives , and substituting this minimizer gives the value , because the matrices commute. The choice costs and costs , so . A column has a small score when its feature vector can be reproduced, up to an error priced by , by a short combination of feature vectors; this is the precise sense in which the score accounts for correlations among columns.
When , . Draw independently with replacement, with
A repeated index is a valid draw but adds no new direction. Let be the set of distinct drawn indices, and . The approximation is . Equivalently, with and the orthogonal projection onto the span of for , the previously established landmark projection identity gives . We write .
If , the vector is zero. Since the first factor is invertible, too. Such a column contains no feature direction, so assigning it probability zero loses nothing. If , set without drawing; all conclusions about the residual then hold trivially.
Worked example 16.1.2
(Duplicated columns share their leverage)
Let and . The eigenvalues are and , with unit eigenvector for , so
A single column would have score . Duplicating it lowers each score to , and the total stays below one: the two columns carry one direction, counted fractionally at this scale. In the lens, is the optimal reconstruction of the first feature vector, with cost . Both probabilities equal , and since has rank one, any single draw gives . The theorem with and asks for , that is : the sufficient budget is valid but ignores this exact structure.
Common mistake
(Sampling by diagonal entries)
Diagonal entries ignore correlations. For and , sampling proportional to uses , whereas the leverage scores , with , give . Five draws miss the third direction with probability under diagonal sampling, but only under leverage sampling.
A finite-sample theorem
Theorem 16.1.3
(An elementary ridge leverage guarantee)
Assume , , and . If
then independent leverage draws as above satisfy, with probability at least ,
This is an absolute spectral-error bound at scale , not a relative approximation to in every direction.
The proof has two steps: a covariance estimate for whitened vectors, then a translation of that estimate into the Nyström residual.
Proof
(Step one: a sample covariance in whitened coordinates)
Put . The matrices involved are functions of and commute; thus
For one draw define . Its denominator is positive almost surely, and . If , independence and zero mean of give
Here . Cross terms vanish by independence. Since , Markov's inequality applied to the squared Frobenius norm shows that with probability at least .
The second step uses only the event just obtained; no further probability enters.
Proof
(Step two: turn coverage into a Nyström residual)
On that event, take any orthogonal to all sampled and set . Then is orthogonal to each sampled , so . Consequently
Rearranging yields , where . For arbitrary , choose . This is orthogonal to the landmark span, and
If the desired inequality is immediate; otherwise divide by and square. Hence for every , proving . The probability bound and the assumed budget complete the proof.
Proof X-ray
The role of whitening
The probabilistic step uses only that the draws are independent and that whenever , so that ; the specific choice is what turns into exactly , and any other choice gives a larger sum by the Cauchy–Schwarz inequality. The key move is in step two. The sample covariance controls only the span of the whitened sampled vectors, while the residual concerns missed original feature directions. A missed direction is tested through , which is orthogonal to every sampled precisely because whitening and unwhitening cancel; then vanishes on , and the operator-norm event bounds . The hypothesis makes invertible, which this change of coordinates requires, and is what allows the rearrangement. The final Cauchy–Schwarz step converts a bound on missed directions into . An unweighted column-count argument provides none of this.
Two directions and a concrete budget
Worked example 16.1.4
(A diagonal Gram matrix)
Let and . The scores are and , so and . With one draw, choosing the first index gives residual ; choosing the second gives . The latter occurs with probability , demonstrating that a positive-probability guarantee is needed.
For and , the theorem's sufficient budget is , so suffices. It guarantees error at most with probability at least . This does not say 79 distinct landmarks are needed: there are only two. In fact error exceeds exactly when all 79 draws choose index 2, an event of probability . The theorem is valid but very conservative in this example.
Counterexample mode
High-probability is not certainty
The same diagonal example shows that independent sampling can miss the dominant direction for every finite : the probability is . Nor does give a relative error bound for some : whenever a positive diagonal direction is missed, its residual equals that direction of exactly.
What does this say about ridge predictions?
For a fixed response vector , compare fitted training vectors
Since both matrices are PSD, each regularized inverse has operator norm at most . The resolvent identity gives
Thus the theorem implies on the same event. For , to demand an error at most , it suffices to choose . The comparison uses the same in both places and the unnormalized convention above. If a loss uses , substitute consistently. The result says nothing by itself about unseen inputs, noisy labels or population generalization.
Worked example 16.1.5
(Comparing fitted vectors after a missed direction)
Return to and , and suppose every draw chose index 1, so and . For ,
The resolvent formula agrees: . Here , which is exactly the theorem's level for , and the bound gives . It is loose by a factor of about because it replaces , which equals on the missed direction, by its norm bound , and is not concentrated on that direction.
Common mistake
(Reading a score or the effective dimension as an error estimate)
The score chooses an index; controls the displayed sufficient sample budget; and measures the realized finite-matrix error. None is itself an estimate of test risk. Computing the exact scores also requires information about the full matrix, so the theorem does not by itself establish a fast algorithm.
Exercises with solutions
Quick check
(Let and . Find the scores, effective dimension and positive sampling probabilities.)
Use for a diagonal matrix.
Solution · Answer
The scores are and . Thus , and . The zero coordinate is never drawn and carries no feature direction.
Quick check
(For with the probabilities in the example, what is the exact probability that the Nyström approximation equals after draws?)
The approximation is exact only when both indices have appeared.
Solution · Answer
Both indices must appear. The two disjoint failure events are that all draws equal 1 or all equal 2. The answer is . For this is zero.
Quick check
(Let with . Show that one leverage draw gives with probability one.)
Find the eigen-decomposition of first.
Solution · Answer
has one positive eigenvalue and . The positive-score indices are precisely those with . Any such column spans the rank-one feature space, so the projection identity gives zero residual.
Quick check
(Why does the proof fail if and is singular?)
Which matrix in the proof must be invertible?
Solution · Answer
and its inverse no longer exist on the whole space. In particular the change of variables used to compare missed feature directions with whitened ones is not valid as written. A separate argument on the range of may be possible, but it is not this theorem.