Implementation

Suppose we have a training set $\{\vec{x}_{i} \in \mathbb{R}^{n} \: : i=1 \: \mbox{to} \: N\}$. We then have the corresponding set of mapped data points in the feature space $\{\Phi(\vec{x}_{i})\}$. We denote centred data points thus: $$\widetilde{\Phi}(\vec{x}) \equiv \Phi(\vec{x}) - \frac{1}{N}\sum\limits_{i=1}^{N}\Phi(\vec{x}_{i})$$

The Kernel PCA algorithm then proceeds as follows:

1. Pick an appropriate kernel function $\mathcal{K}$ (the form of the kernel, plus any parameters).

1. Construct the Kernel Matrix for the mapped data:
$$K_{ij} \equiv\Phi(\vec{x}_{i})\bullet\Phi(\vec{x}_{j})=\mathcal{K}(\vec{x}_{i},\vec{x}_{j}).$$
2. Use this to construct the Covariance Matrix for the centred data:
$$\widetilde{K}_{ij} \equiv \widetilde{\Phi}(\vec{x}_{i})\bul......=1}^{N}K_{qj}+ \frac{1}{N^{2}}\sum\limits_{p,q=1}^{N}K_{pq}$$
3. Solve for the set of eigenvectors $\{{b}^{\alpha}_{i}: i=1 \: \mbox{to} \:\: N, \alpha=1 \:\: \mbox{to} \:\: M \}$ of the matrix $\widetilde{K}_{ij}$, which give us our set of basis vectors $\{\boldsymbol{b}^{\alpha}\}$ in feature space thus:
$$\lambda^{\alpha}b^{\alpha}_{i} = \frac{1}{N}\sum\limits_{j=......symbol{b}^{\alpha} \propto \, b^{\alpha}_{i}\Phi(\vec{x}_{i})$$
4. The unnormalised KPCA components of a test point $\vec{x}$ are then given by:
$$p^{\alpha}(\vec{x}) \propto \boldsymbol{b}^{\alpha}\bullet\......its_{i=1}^{N}b^{\alpha}_{i}\mathcal{K}(\vec{x},\vec{x}_{i})$$





The exact values of the components depend on the normalisation chosen for the set of vectors $\{\boldsymbol{b}^{\alpha}\}$, which will always form an orthogonal basis, but need not be orthonormal. The value of a component can also be shifted so that the mean of each component over the data is then zero.

2001-10-02