Kernel PCA

The goal of the ordinary PCA (Principal Component Analysis) is to find a set of orthogonal directions such that the variance of the projected data is maximized. Assume we have samples \(\{x_{i}\}_{i=1}^{n}\). This idea can be formalized as \[ u_{1}=\arg\max_{\|u\|\leq1}\frac{1}{n}\sum_{i=1}^{n}\left(u^{\top}x_{i}-u^{\top}\bar{x}\right)^{2} \] where \(\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}\) and \(u\) is the direction we wish to find. Define \(C=\frac{1}{n}XHX^{\top}\) where \[\begin{eqnarray*} X & = & \left(x_{1}|\cdots|x_{n}\right)\\ H & = & I-\frac{1}{n}\boldsymbol{1}\boldsymbol{1}^{\top}. \end{eqnarray*}\] Then the PCA problem can be solved by considering the eigenvalue problem: \[ Cu=\lambda u. \]

KPCA

In kernel PCA or KPCA, the goal is to do PCA in the feature space. That is \(\{x_{i}\}_{i=1}^{n}\) are mapped into a high (or even infinite) dimensional space and PCA is carried out in that space. Let \(\phi\) be such feature map. KPCA can be formalized as \[ f_{1}=\arg\max_{\|f\|_{\mathcal{H}}\leq1}\frac{1}{n}\sum_{i=1}^{n}\left\langle f,\phi(x_{i})-\bar{\phi}\right\rangle _{\mathcal{H}}^{2} \] where \(\bar{\phi}=\frac{1}{n}\sum_{i=1}^{n}\phi(x_{i})\), \(f\) is the direction (can be infinite-dimensional) we wish to find, and \(\mathcal{H}\) is assumed to be a reproducing kernel Hilbert space with the inner product given by a kernel \(k\) i.e., \(\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}=k(x,y)\). Let \(\tilde{\phi}_{i}:=\phi(x_{i})-\bar{\phi}\) for convenience. The squared inner product in the sum can be simplified as \[\begin{eqnarray*} \left\langle f,\tilde{\phi}_{i}\right\rangle _{\mathcal{H}}^{2} & = & \left\langle f,\tilde{\phi}_{i}\right\rangle _{\mathcal{H}}\left\langle f,\tilde{\phi}_{i}\right\rangle _{\mathcal{H}}=\left\langle f,\left\langle f,\tilde{\phi}_{i}\right\rangle _{\mathcal{H}}\tilde{\phi}_{i}\right\rangle _{\mathcal{H}}\\ & = & \left\langle f,\left(\tilde{\phi}_{i}\otimes\tilde{\phi}_{i}\right)f\right\rangle _{\mathcal{H}}. \end{eqnarray*}\] With this form, the optimization problem can be rewritten as \[ f_{1}=\arg\max_{\|f\|_{\mathcal{H}}\leq1}\left\langle f,Cf\right\rangle _{\mathcal{H}} \] where \(C:=\frac{1}{n}\sum_{i=1}^{n}\tilde{\phi}_{i}\otimes\tilde{\phi}_{i}\). Notice that \(Cf\) involves an inner product of \(f\) and \(\tilde{\phi}_{i}\). This implies that if \(f\) has any component orthogonal to \(\tilde{\phi}_{i}\), it will vanish after taking the inner product. Hence, we can conclude that \(f\) must be a linear combination of \(\{\tilde{\phi}_{i}\}_{i}\) (lie in the span of \(\{\tilde{\phi}_{i}\}_{i}\)): \[ f_{l}=\sum_{i=1}^{n}\alpha_{li}\tilde{\phi}_{i}=\tilde{X}\boldsymbol{\alpha}_{l} \] where we define \(\tilde{X}:=\left(\tilde{\phi}_{1}|\cdots|\tilde{\phi}_{n}\right)\) and \(\boldsymbol{\alpha}_{l}\) are coefficients. With the definition of \(\tilde{X}\), we have \(C=\frac{1}{n}\tilde{X}\tilde{X}^{\top}\).

Eigenvalue problem for KPCA

The KPCA can be solved by considering the following eigenvalue problem. \[ f_{l}\lambda_{l}=Cf_{l} \] Recall that \(f_{l}\) can be infinite-dimensional. To solve the problem, we multiply both sides to the left by \(\tilde{X}^{\top}\). \[ \tilde{X}^{\top}f_{l}\lambda_{l}=\tilde{X}^{\top}\tilde{X}\boldsymbol{\alpha}_{l}\lambda_{l}=\tilde{K}\boldsymbol{\alpha}_{l}\lambda_{l} \] where \(\tilde{K}:=\tilde{X}^{\top}\tilde{X}=HKH\) is the centered gram matrix. For the right hand side, \[\begin{eqnarray*} \tilde{X}^{\top}Cf_{l} & = & \frac{1}{n}\tilde{X}^{\top}\tilde{X}\tilde{X}^{\top}f_{l}=\frac{1}{n}\tilde{X}^{\top}\tilde{X}\tilde{X}^{\top}\tilde{X}\boldsymbol{\alpha}_{l}\\ & = & \frac{1}{n}\tilde{K}^{2}\boldsymbol{\alpha}_{l}. \end{eqnarray*}\] Equating the previous two equations, we have \[ n\lambda_{l}\tilde{K}\boldsymbol{\alpha}_{l}=\tilde{K}^{2}\boldsymbol{\alpha}_{l}\iff n\lambda_{l}\boldsymbol{\alpha}_{l}=\tilde{K}\boldsymbol{\alpha}_{l} \] which is just an \(n\)-dimensional eigenvalue problem.

Norm constraint of KPCA

Recall that we have the constraint \(\|f\|_{\mathcal{H}}\leq1\). Since the maximization problem benefits from scaling up \(f\), the solution will satisfy \(\|f\|_{\mathcal{H}}=1=\|f\|_{\mathcal{H}}^{2}\). \[\begin{eqnarray*} \|f\|_{\mathcal{H}}^{2} & = & 1=\left\langle \tilde{X}\boldsymbol{\alpha},\tilde{X}\boldsymbol{\alpha}\right\rangle _{\mathcal{H}}\\ & = & \boldsymbol{\alpha}\tilde{K}\boldsymbol{\alpha}\\ & = & n\lambda\boldsymbol{\alpha}^{\top}\boldsymbol{\alpha}=1 \end{eqnarray*}\] where we use the identity from the eigenvalue equation in the last two lines. The last line implies that \[ \|\boldsymbol{\alpha}\|_{\mathcal{H}}^{2}=\frac{1}{n\lambda}\iff\|\boldsymbol{\alpha}\|_{\mathcal{H}}=\frac{1}{\sqrt{n\lambda}}. \] This means that to force the norm constraint \(\|f\|_{\mathcal{H}}=1\), we need to make sure that \(\|\boldsymbol{\alpha}\|_{\mathcal{H}}=\frac{1}{\sqrt{n\lambda}}\). This can be done by renormalizing \(\boldsymbol{\alpha}\) obtained from the eigenvalue problem by \[ \boldsymbol{\alpha}\leftarrow\frac{\boldsymbol{\alpha}}{\|\boldsymbol{\alpha}\|_{2}}\frac{1}{\sqrt{n\lambda}}. \]

KPCA projection

Define the projection operator \(P_{d}\) for projection onto the first \(d\) eigenvectors as \[\begin{eqnarray*} P_{d}\phi(x^{*}) & = & \sum_{i=1}^{d}P_{f_{i}}\phi(x^{*})\\ P_{f}\phi(x^{*}) & = & \left\langle f,\phi(x^{*})\right\rangle _{\mathcal{H}}f. \end{eqnarray*}\] Given a new point \(x^{*}\) its projection can be found with \[ y^{*}=\arg\min_{y\in\mathcal{X}}\|\phi(y)-P_{d}\phi(x^{*})\|_{\mathcal{H}}^{2}. \] This is useful, for example, in image denoising where \(x^{*}\) is a noisy image, and a denoised (projected) image \(y^{*}\) is the goal.

KPCA coordinates

If dimensionality reduction or visualization is the goal, then the projection step is not needed. In these cases, one simply needs the first \(d\) coordinates (where \(d\) is usually chosen to be low). The \(d\) coordinates are given by \[ \left(\begin{array}{c} \left\langle \phi(x^{*}),f_{1}\right\rangle _{\mathcal{H}}\\ \left\langle \phi(x^{*}),f_{2}\right\rangle _{\mathcal{H}}\\ \vdots\\ \left\langle \phi(x^{*}),f_{d}\right\rangle _{\mathcal{H}} \end{array}\right)=\left(\begin{array}{c} \left\langle \phi(x^{*}),\tilde{X}\boldsymbol{\alpha}_{1}\right\rangle _{\mathcal{H}}\\ \left\langle \phi(x^{*}),\tilde{X}\boldsymbol{\alpha}_{2}\right\rangle _{\mathcal{H}}\\ \vdots\\ \left\langle \phi(x^{*}),\tilde{X}\boldsymbol{\alpha}_{d}\right\rangle _{\mathcal{H}} \end{array}\right)=\left(\begin{array}{c} \sum_{i=1}^{n}\tilde{k}(x^{*},x_{i})\alpha_{1,i}\\ \sum_{i=1}^{n}\tilde{k}(x^{*},x_{i})\alpha_{2,i}\\ \vdots\\ \sum_{i=1}^{n}\tilde{k}(x^{*},x_{i})\alpha_{d,i} \end{array}\right). \] Note that \(f_{1}\) corresponds to the largest eigenvector, \(f_{2}\) the second largest, and so on.