Why select columns of a kernel matrix?
A kernel Gram matrix records inner products between all pairs of observed feature vectors. With observations it has entries, even when much of its geometry can be described by a smaller collection of directions. One way to reduce the calculation is to choose observations as landmarks, evaluate similarities to those observations, and reconstruct the remaining inner products from them.
The reconstruction needs more than a product of the selected columns. Those columns are coordinates measured against landmark vectors that need not be orthogonal or independent. Their own Gram matrix tells us how to correct this coordinate system. An inverse performs that correction when the landmarks are independent; a pseudoinverse handles the dependent case. The resulting Nyström matrix has a particularly useful interpretation: it is the Gram matrix after orthogonally projecting every feature vector onto the landmark span.
We will prove this interpretation for a fixed finite positive semidefinite matrix. It explains exactly what is preserved and exactly which directions are lost. It does not require random landmarks, and it does not imply that an arbitrary selection is accurate or that a fitted predictor generalizes to new data.
Matrices, landmarks, and a singular inverse
Let be symmetric and positive semidefinite, abbreviated PSD: for every . Choose distinct indices , where , and put
Thus contains the selected columns and is their principal intersection. The assumption that is a principal submatrix of the same PSD matrix matters. An unrelated positive semidefinite matrix of size cannot simply be substituted for in the conclusions below.
Definition 14.1.1
(The PSD pseudoinverse and Nyström matrix)
Write the positive part of an orthonormal eigendecomposition of as , where , , and has the strictly positive eigenvalues on its diagonal. Define
The pseudoinverse acts as zero on . When , the products are interpreted as zero matrices, with having zero columns. If is invertible, .
The feature matrix has columns, even if landmark indices were selected. Repeated feature directions do not create new information. The definition shows immediately that is PSD and has rank at most . It takes further work to prove that its difference from is PSD and that its selected columns are exact.
For symmetric matrices, means is PSD. This is an order on quadratic forms; it is not an entrywise inequality. We use for the Euclidean operator norm and for the trace.
Projection explains the entire construction
Theorem 14.1.2
(Landmark projection and positive semidefinite error)
For the stated finite PSD matrix and landmark set, choose any factorization , with , and put . Such a factorization exists by the spectral theorem; one may take and . Define
Then is the orthogonal projection onto , and
Moreover , and if and only if all transposed rows of belong to the landmark span , equivalently .
Building the projection rather than assuming it
The proof constructs an orthonormal basis of the landmark span from the eigenvectors of , so that is visibly a projection.
Proof
(Orthonormal landmark directions give the projection)
First and . If is a unit eigenvector of with eigenvalue , define . Direct multiplication gives
These vectors form an orthonormal basis of . To see that none of this range is missed, observe that . Hence , and every zero-eigenvalue component of a vector vanishes after applying . The positive-eigenvalue vectors therefore generate the whole range. It follows that
This matrix fixes the landmark span and annihilates its orthogonal complement. In particular and . Substitution of now proves . For every ,
This establishes the PSD error without subtracting unrelated PSD matrices. Since every landmark row is already in the projected span, projection leaves its inner product with every projected data row equal to its original inner product. Algebraically, , so .
Finally holds precisely when : in one direction this is immediate; in the other take the trace of to obtain the sum of squared residual lengths. Thus every data feature lies in the landmark span. Since the landmark row span is contained in the data row span, equality of their dimensions is equivalent to equality of the spans. Those dimensions are and .
Proof X-ray
Why a singular landmark matrix is still consistent
The proof uses the PSD hypothesis exactly once, to factor ; everything after that is geometry of the rows of . The second hypothesis is that and come from the same matrix, which is what makes and share the factor .
The key move is , hence . It is used twice. It shows that the positive eigenvectors of already span the landmark directions, so misses nothing; and it shows that a singular causes no inconsistency: if , then and , so . The pseudoinverse discards only combinations already equal to zero, never a hidden nonzero selected column. Once is known to be an orthogonal projection, the PSD residual and the exact selected columns are one-line consequences. The counterexample below, an indefinite matrix, is exactly a case where .
The singular Schur complement and its missing hypothesis
Reorder the observations so that landmarks come first. Write
The expression is the generalized Schur complement. When is singular, positive semidefiniteness of this complement, even together with , is not enough to prove that an arbitrary symmetric block matrix is PSD.
Theorem 14.1.3
(A precise singular block-matrix criterion)
A real symmetric matrix is PSD if and only if all three conditions hold: , , and .
Both directions rest on the same quadratic-form computation.
Proof
(Kernel vectors force the range condition; completing the square does the rest)
If is PSD, then so is its principal block . For , fix any vector of the size of the lower block and consider the quadratic form at . Its value is and must be nonnegative for every real . Therefore . Taking orthogonal complements gives , because is symmetric.
Under this range condition, . Completing the square gives, for arbitrary ,
Choosing shows that PSD of forces PSD of the complement. Conversely, the completed-square expression is nonnegative when the three conditions hold. This proves the criterion and explains the zero off-diagonal blocks of the Nyström residual.
Counterexample mode
The pseudoinverse does not repair an indefinite input
Take and select its first index. Then , , , and . The generalized Schur complement is zero, yet is indefinite: the vector has quadratic form . The range condition fails because while . The formula produces and does not reproduce the selected column. The original PSD hypothesis prevents exactly this inconsistency.
A complete calculation with dependent landmarks
Worked example 14.1.4
(Two landmarks, only one retained direction)
Use the four feature rows , , , and . Their Gram matrix is
Choose the first two observations. Then
The sole positive eigenvalue is , with eigenvector . Therefore . Calling this column and writing gives
Taking to be the matrix of the listed feature rows, we have : the landmarks retain the first coordinate and lose the second. The selected columns are exact, but entry changes from to . Exact selected-column recovery is therefore weaker than exact matrix recovery.
To project the third feature, solving gives . Every such coefficient vector reconstructs the same projected feature ; the pseudoinverse chooses the coefficient vector of least Euclidean length. Adding the third observation as a landmark spans both coordinates and makes the approximation exact. Merely adding another multiple of the first feature would not do so.
What can be certified without a sampling theorem?
Let be the transpose of row of , and put . Then . In particular
The entry bound is Cauchy–Schwarz. The norm bound follows because all eigenvalues of are nonnegative, so the largest is at most their sum. These are deterministic certificates for the selected finite matrix. Computing the diagonal residuals needs the original diagonal entries as well as the selected columns; it does not require every unselected pairwise entry.
Worked example 14.1.5
(Certificates computed from the selected columns only)
Return to the four-point example with landmarks , and pretend that only the diagonal of and the selected columns are known. For row , and
so . For row , , so ; the landmark rows give . The certificates are and . The full calculation found , with and : both bounds are attained here because the residual has rank one. With a residual of higher rank, the trace bound overestimates the operator norm.
Common mistake
(Reading the PSD order as an entrywise inequality)
does not say . Take feature rows , , with the first as the only landmark. Projection onto the first coordinate sends both other rows to , so while , and . Only the diagonal residuals are guaranteed nonnegative; off-diagonal residual entries are controlled in absolute value by .
More landmarks cannot worsen this PSD error in exact arithmetic. If every index of also appears in a landmark tuple , their feature spans are nested. Decomposing the larger span into the smaller span plus an orthogonal complement shows that is an orthogonal projection. Consequently and . A new dependent landmark leaves the span unchanged and produces no improvement.
Worked example 14.1.6
(A legal selection can miss the main direction)
For , select only the second index. Then and the operator error is . Selecting the first index instead gives error . Both approximations preserve selected columns and have PSD residuals. The ratio can be made arbitrarily large by replacing by a larger number. Thus the number of landmarks alone supplies no relative accuracy guarantee for arbitrary selections.
If comes from a genuine PSD kernel , the same construction defines a kernel away from the training set. The landmark inputs are . Set and use
It is PSD because it has feature vector . In the original reproducing space it is the inner product between projections of the sections and onto the landmark-section span. The same projection proof makes PSD on every finite set. This statement supplies no uniform smallness bound over an entire domain. A small residual on the training inputs can coexist with a large residual at an unobserved input.
Numerical modifications change the statement
The pseudoinverse in the theorem is the exact one. In numerical computation, tiny positive eigenvalues require a tolerance decision. Retaining only some positive modes produces a projection onto a smaller subspace; the residual is still PSD, but selected-column equality may be lost. A tolerance must not be described as an exact algebraic rank test.
Replacing by for is another modification. With , the corresponding middle matrix is . Its eigenvalues on the positive landmark directions are , and its other eigenvalues are zero. Thus it lies between zero and the identity and is an orthogonal projection only in the trivial case . The regularized approximation still lies between zero and . If , the selected block changes, so exact selected-column recovery fails. For the one-entry matrix and , the approximation is , not . This landmark regularization is also distinct from the ridge penalty used later to fit labels.
Concept lensStructural
Three questions that require different evidence
The projection theorem asks whether the approximation respects kernel geometry. Residual estimates or a sampling theorem ask whether it approximates a specified matrix accurately. A learning theorem asks how a fitted function performs on new observations. Positive semidefiniteness answers the first question; it does not answer the other two. Nyström coordinates use selected data landmarks and give a deterministic lower approximation for fixed landmarks. The random-feature construction in the preceding note instead gives an entrywise unbiased estimate of under its specified feature-sampling law; it need not be below in PSD order.
Exercises
Quick check
(Let with , and choose the second index as the sole landmark. Compute , , and . Why is the sign of the feature coordinate harmless, and what changes if the selected coordinate of is zero?)
Solution · Answer
Here and . Taking the positive eigenvector of this scalar block to be gives , so . Multiplying every feature by leaves pairwise inner products unchanged. If the selected coordinate is zero, then and , so the approximation is zero; it is exact only when the entire vector is zero. A rank-one matrix can therefore be recovered by one informative landmark but not by every landmark.
Quick check
(Let , and . Determine exactly which real make the full block matrix PSD, and compute the Nyström residual for with the first two indices as landmarks.)
Solution · Answer
The pseudoinverse is . The column belongs to the span of , which is , and . The singular block criterion therefore gives exactly . At , the full residual is ; its trace and operator norm are both . For , choosing and the lower coefficient gives the negative quadratic form .
Quick check
(The unselected diagonal residuals are and , and all selected residuals are zero. Bound the absolute residual entry between the two unselected observations and bound . Can both bounds be attained?)
Solution · Answer
Cauchy–Schwarz gives . The trace bound gives . Both are attained by the rank-one unselected block , the Gram matrix of two collinear residual features of lengths and . Appending a separate orthogonal landmark feature realizes it as the residual of a PSD Gram matrix.
Quick check
(For the linear kernel on , the only training input and landmark is . Compute the training matrix error and the kernel diagonal error at , where . What does this show about domain-wide estimates?)
Solution · Answer
The training matrix and its approximation are both , so the training error is zero. The landmark records only the first coordinate, giving . At , the true diagonal is and the approximate diagonal is zero, so the diagonal error is , arbitrarily large on this unbounded domain. Exactness on a finite training set supplies no uniform domain estimate without further assumptions controlling the unobserved directions.