Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 218 / 6 / c

For $\varphi (x)=x$ and centered data, the objective is the Rayleigh quotientThis is the first-direction optimization in principal component analysis. Therefore $\hat{u}$ is any unit eigenvector of the sample covariance matrix $S$ corresponding to its largest eigenvalue.

Write $\Phi \alpha ={\sum }_i{\alpha }_i\varphi (X_i)$. By the definition of the kernel matrix,andThe irrelevant positive factor $1/n$ gives exactly the stated constrained optimization.

Let $K{v}_1={\lambda }_1{v}_1$, where ${\lambda }_1>0$ is the largest eigenvalue and $\Vert v_1{\Vert }_2=1$. The generalized Rayleigh quotient is maximized byup to sign and addition of a vector in $\ker K$, which does not change $\hat{u}=\Phi \hat{\alpha }$. Repeated leading eigenvectors give further principal directions.

Kernel principal component analysis diagonalizes the centered $n$ by $n$ kernel matrix instead of an explicit covariance operator in a possibly infinite-dimensional feature space. A new point has coordinateso the leading coordinates require only evaluations of the positive-semidefinite kernel.

Running the K-nearest neighbors algorithm in a truncated collection of these coordinates can remove low-variance noise, reduce effective dimension, and allow a nonlinear boundary in the original covariates. This is the kernel trick: every feature-space inner product needed for fitting and projection is replaced by $k(x,z)=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ without constructing $\varphi (x)$ explicitly.