7
$\begingroup$

In kernel PCA (principal component analysis) you first choose a desired kernel, use it to find your $K$ matrix, center the feature space via the $K$ matrix, find its eigenvalues and eigenvectors, then multiply the centered kernel matrix by the desired eigenvectors corresponding to the largest eigenvalues.

The result should be the projection of the feature space data onto a low dimensional subspace.

To the best of my knowledge, you divide the eigenvalues by the number $n$ of original data points to scale them. So the question is, do the eigenvectors you choose to multiply the centered kernel matrix by need scaling as well and if so how do you do it?

$\endgroup$
7
$\begingroup$

To find PCs in classical PCA, one can perform singular value decomposition of the centred data matrix (with variables in columns) $\mathbf X = \mathbf U \mathbf S \mathbf V^\top$; columns of $\mathbf U \mathbf S$ are called principal components (i.e. projections of the original data onto the eigenvectors of the covariance matrix). Observe that the so called Gram matrix $\mathbf G = \mathbf X \mathbf X^\top = \mathbf U \mathbf S^2 \mathbf U^\top$ has eigenvectors $\mathbf U$ and eigenvalues $\mathbf S^2$, so another way to compute principal components is to scale eigenvectors of the Gram matrix by the square roots of the respective eigenvalues.

In full analogy, here is a complete algorithm to compute kernel principal components:

  1. Choose a kernel function $k(\mathbf x, \mathbf y)$ that conceptually is a scalar product in the target space.

  2. Compute a Gram/kernel matrix $\mathbf K$ with $K_{ij} = k(\mathbf x_{(i)}, \mathbf x_{(j)})$.

  3. Center the kernel matrix via the following trick: $$\mathbf K_\mathrm{centered} = \mathbf K - \mathbf 1_n \mathbf K - \mathbf K \mathbf 1_n + \mathbf 1_n \mathbf K \mathbf 1_n=(\mathbf I - \mathbf 1_n)\mathbf K(\mathbf I - \mathbf 1_n) ,$$ where $\mathbf 1_n$ is a $n \times n$ matrix with all elements equal to $\frac{1}{n}$, and $n$ is the number of data points.

  4. Find eigenvectors $\mathbf U$ and eigenvalues $\mathbf S^2$ of the centered kernel matrix. Multiply each eigenvector by the square root of the respective eigenvalue.

  5. Done. These are the kernel principal components.

Answering your question specifically, I don't see any need of scaling either eigenvectors or eigenvalues by $n$ in steps 4--5.

A good reference is the original paper: Scholkopf B, Smola A, and Müller KR, Kernel principal component analysis, 1999. Note that it presents the same algorithm in a somewhat more complicated way: you are supposed to find eigenvectors of $K$ and then multiply them by $K$ (as you wrote in your question). But multiplying a matrix and its eigenvector results in the same eigenvector scaled by the eigenvalue (by definition).

$\endgroup$
  • $\begingroup$ Thank you for the answer. I'd like to ask you a question. I've read the paper "Nonlinear Component Analysis as a Kernel Eigenvalue Problem"of Scholkopf, Smola and Müller. In this paper, at appendix B, the authors calculate the eigenvectors $\tilde{\alpha}^k$ and eigenvalues $\tilde{\lambda}^k$ of the centered K matrix and then they normalize the eigenvectors $\tilde{\alpha}^k$ so that they have length equal to $\frac{1}{\sqrt{\tilde{\lambda}^k}}$. Does the algorithm based on an eigen-decomposition of the centered K matrix include this normalization step? Thank you in advance. $\endgroup$ – John M Jan 24 '17 at 21:36
  • $\begingroup$ @JohnM See here stats.stackexchange.com/questions/126014 about normalization. $\endgroup$ – amoeba Jan 24 '17 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.