Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 218 / 4

A real positive-semidefinite kernel is a symmetric function $k:X\times X\to \mathbb{R}$ such that every finite Gram matrix $(k(x_i,x_j))$ is positive semidefinite. The Moore-Aronszajn theorem says that there are a Hilbert space $H$ and a feature map $\varphi :X\to H$ such thatEquivalently, $H$ can be chosen as the unique Reproducing-kernel Hilbert space with reproducing kernel $k$.

Solved by gpt-5.6-sol high.

Let $(e_{r,a},e_{r,b}{)}_{r=1}^L$ be the standard orthonormal basis of ${\mathbb{R}}^{2L}$ and defineThenThus $g$ is a positive-semidefinite kernel.

Solved by gpt-5.6-sol high.

The empirical kernel covariance operator $\Sigma$ is self-adjoint and positive semidefinite. Maximize $⟨u,\Sigma u⟩$ subject to $⟨u,u⟩=1$. The first variation of the Lagrange multiplier functional givesso $\Sigma v=\lambda v$. Taking the inner product with $v$ gives

Solved by gpt-5.6-sol high.

Positive definiteness of $K$ makes the vectors $\varphi (x_1),\dots ,\varphi (x_n)$ linearly independent. In particular $\Sigma \ne 0$, so the maximum Rayleigh quotient is positive and $\lambda >0$. The eigenvector equation giveswhich lies in their span. Hence $v={\sum }_i{\alpha }_i\varphi (x_i)$ for some $\alpha \in {\mathbb{R}}^n$.

Solved by gpt-5.6-sol high.

Substituting $v={\sum }_j{\alpha }_j\varphi (x_j)$ into $\Sigma v=\lambda v$ givesLinear independence yields $K\alpha =n\lambda \alpha$. The unit-norm constraint gives

Solved by gpt-5.6-sol high.

The feature space may be extremely high-dimensional or infinite-dimensional, and $\varphi$ may be known only implicitly. Instead, compute the leading eigenvector $\alpha$ of the kernel matrix $K$, normalize it by ${\alpha }^{\top }K\alpha =1$, and use the kernel trick:This requires only kernel evaluations.

Solved by gpt-5.6-sol high.

Kernel principal component analysis can represent nonlinear low-dimensional structure by performing linear PCA in a nonlinear feature space. It can also work directly with structured objects such as strings through a kernel, without assigning them explicit finite-dimensional coordinates. Both capabilities are unavailable to ordinary linear PCA on the original variables.

Solved by gpt-5.6-sol high.