Kernel Principal Component Analysis

Introduction

A new method for performing a nonlinear form of Principal Component Analysis is proposed. By the use of integral operator kernel functions, one can efficiently compute principal components in high-dimensional feature spaces, related to input space by some nonlinear map; for instance the space of all possible $d$-pixel products in images. This paper gives the derivation of the method of presents experimental results on polynomial feature extraction for pattern recognition.

Assume for the moment that our data mapped into feature space, $\varphi ({\mathbf{\text{x}}}_1),\dots ,\varphi ({\mathbf{\text{x}}}_{\ell })$, is centered, i.e. ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^{\ell }\varphi ({\mathbf{\text{x}}}_{\ell })=0$. To do PCA for the covariance matrix

$$\stackrel{�}{C}=\frac{1}{\ell }\sum _{j=1}^{\ell }\varphi ({\mathbf{\text{x}}}_j)\varphi {({\mathbf{\text{x}}}_j)}^{\text{T}}$$

we have to find Eigenvalues $\lambda \ge 0$ and Eigenvectors $\mathbf{\text{V}}\in F\{\}$ satisfying $\lambda \mathbf{\text{X}}=\stackrel{�}{C}\mathbf{\text{V}}$. All solutions $\mathbf{\text{V}}$ lie in the span of $\varphi ({\mathbf{\text{x}}}_1),\dots ,\varphi ({\mathbf{\text{x}}}_{\ell })$. This implies that we may consider the equivalent system

$$\lambda (\varphi ({\mathbf{\text{x}}}_k)\cdot \mathbf{\text{V}})=(\varphi ({\mathbf{\text{x}}}_k)\cdot \stackrel{�}{C}\mathbf{\text{V}})\text{ for all }k=1,\dots ,\ell ,$$

and that there exists equivalent coefficients ${\alpha }_1,\dots ,{\alpha }_{\ell }$ such that

$$\mathbf{\text{V}}=\sum _{i=1}^{\ell }{\alpha }_i\varphi ({\mathbf{\text{x}}}_i)$$

Substituting and defining an $\ell \times \ell$ matrix $K$ by

$$K_{\mathit{ij}}:=(\varphi ({\mathbf{\text{x}}}_i)\cdots \varphi ({\mathbf{\text{x}}}_j))$$

we arrive at

$$\mathit{\ell \lambda K\alpha }=K^2\alpha$$

where $\alpha$ denotes the column vector with entries ${\alpha }_1,\dots ,{\alpha }_{\ell }$. To find solutions to the above, we solve the Eigenvalue problem

$$\mathit{\ell \lambda \alpha }=\mathit{K\alpha }$$

for nonzero Eigenvalues. We normalize the solutions ${\alpha }^k$ belonging to nonzero Eigenvalues by requiring that the corresponding vectors in $F$ be normalized, i.e. $({\mathbf{\text{V}}}^k\cdot {\mathbf{\text{V}}}^k)=1$. This translates to:

$$1=\sum _{i,j=1}^{\ell }{\alpha }_i^k{\alpha }_j^k(\varphi ({\mathbf{\text{x}}}_i)\varphi ({\mathbf{\text{x}}}_j))=({\alpha }^k\cdot K{\alpha }^k)={\lambda }_k({\alpha }^k\cdot {\alpha }^k)$$

For princupal component extraction, we compute projections of the image of a test point $\varphi (\mathbf{\text{x}})$ onto the Eigenvectors ${\mathbf{\text{V}}}^k$ in $F$ according to

$$({\mathbf{\text{V}}}^k\cdot \varphi (\mathbf{\text{x}})=\sum _{i=1}^{\ell }{\alpha }_{i=1}^k(\varphi ({\mathbf{\text{x}}}_i)\cdot \varphi (\mathbf{\text{x}}))$$

Kernels that have been successfully used in support vector machines include polynomial kernels, radial basis functions, and sigmoid kernels.