Kernel PCA

Background Knowledge

Kernel PCA is a technique used for dimensionality reduction that extends traditional Principal Component Analysis (PCA) by using the kernel trick to find nonlinear projections. In traditional PCA, we find linear projections that capture the most variance in the data. However, many real-world datasets have nonlinear relationships between features, which cannot be captured by linear projections. This is where Kernel PCA comes in – it uses a kernel function to map the data into a higher-dimensional space, where linear projections can capture nonlinear relationships in the original space.

The RBF (Radial Basis Function) kernel is a commonly used kernel function, which computes the similarity between two points $x_i$ and $x_j$ as $K_{ij} = \exp(-\|x_i - x_j\|^2 / (2\sigma^2))$. The kernel matrix $K$ is a matrix where the entry at row $i$ and column $j$ is the similarity between points $x_i$ and $x_j$. The centering step is necessary to ensure that the kernel matrix is zero-mean, which is a requirement for PCA. Centering involves subtracting the mean of each row and column from the kernel matrix.

The eigendecomposition of the centered kernel matrix $\tilde{K}$ gives us the eigenvalues and eigenvectors, which represent the amount of variance captured by each projection and the direction of the projection, respectively. The power iteration method is an efficient way to find the dominant eigenvector, which corresponds to the projection that captures the most variance. By scaling the eigenvector columns by $\sqrt{\lambda}$, we can obtain the projected values.