32
$\begingroup$

If in kernel PCA I choose a linear kernel $K(\mathbf{x},\mathbf{y}) = \mathbf x^\top \mathbf y$, is the result going to be different from the ordinary linear PCA? Are the solutions fundamentally different or does some well defined relation exist?

$\endgroup$

3 Answers 3

43
$\begingroup$

Summary: kernel PCA with linear kernel is exactly equivalent to the standard PCA.

Let $\mathbf{X}$ be the centered data matrix of $N \times D$ size with $D$ variables in columns and $N$ data points in rows. Then the $D \times D$ covariance matrix is given by $\mathbf{X}^\top\mathbf{X}/(n-1)$, its eigenvectors are principal axes and eigenvalues are PC variances. At the same time, one can consider the so called Gram matrix $\mathbf{X}\mathbf{X}^\top$ of the $N \times N$ size. It is easy to see that it has the same eigenvalues (i.e. PC variances) up to the $n-1$ factor, and its eigenvectors are principal components scaled to unit norm.

This was standard PCA. Now, in kernel PCA we consider some function $\phi(x)$ that maps each data point to another vector space that usually has larger dimensionality $D_\mathrm{new}$, possibly even infinite. The idea of kernel PCA is to perform the standard PCA in this new space.

Since the dimensionality of this new space is very large (or infinite), it is hard or impossible to compute a covariance matrix. However, we can apply the second approach to PCA outlined above. Indeed, Gram matrix will still be of the same manageable $N \times N$ size. Elements of this matrix are given by $\phi(\mathbf{x}_i)\phi(\mathbf{x}_j)$, which we will call kernel function $K(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)\phi(\mathbf{x}_j)$. This is what is known as the kernel trick: one actually does not ever need to compute $\phi()$, but only $K()$. Eigenvectors of this Gram matrix will be the principal components in the target space, the ones we are interested in.

The answer to your question now becomes obvious. If $K(x,y)=\mathbf{x}^\top \mathbf{y}$, then the kernel Gram matrix reduces to $\mathbf{X} \mathbf{X}^\top$ which is equal to the standard Gram matrix, and hence the principal components will not change.

A very readable reference is Scholkopf B, Smola A, and Müller KR, Kernel principal component analysis, 1999, and note that e.g. in Figure 1 they explicitly refer to standard PCA as the one using dot product as a kernel function:

kernel PCA

$\endgroup$
5
  • $\begingroup$ were are those pictures from in your answer? From some book? $\endgroup$ Jan 21, 2015 at 3:43
  • $\begingroup$ @Pinocchio, the figure is taken from the Scholkopf et al. paper, referenced and linked to in my answer. $\endgroup$
    – amoeba
    Jan 21, 2015 at 9:38
  • $\begingroup$ "It is easy to see that it has the same eigenvalues (i.e. PC variances) up to the n−1 factor" - wouldn't this mean that they are not completely equivalent then? Let's say I have a matrix with n=10 samples, d=200 dimensions. In standard PCA I would be able to project the data to 199 dimensions if I wanted, but in kernel PCA with linear kernel I can only up to 10 dimensions. $\endgroup$
    – Cesar
    Jan 26, 2016 at 9:28
  • 1
    $\begingroup$ @Cesar, no, if you have n=10 samples then the covariance matrix will have rank 10-1=9 and standard PCA will only find 9 dimensions (as well as kernel PCA). See here: stats.stackexchange.com/questions/123318. $\endgroup$
    – amoeba
    Jan 26, 2016 at 10:14
  • $\begingroup$ I'm getting file not found for the reference link of Scholkopf B, Smola A, and Müller KR. $\endgroup$
    – pbible
    Nov 24, 2016 at 4:44
6
$\begingroup$

In addition to amoeba's nice answer, there is an even simpler way to see the equivalence. Again let $X$ be the data matrix of $N \times D$ size with $D$ variables in columns and $N$ data points in rows. Standard PCA corresponds to taking a singular value decomposition of the matrix $X = U \Sigma V^\top$ with $U$ the principal components of $X$. The singular value decomposition of the linear kernel $XX^\top = U \Sigma^2 U^\top$ has the same left singular vectors and so the same principal components.

$\endgroup$
2
  • $\begingroup$ For standard PCA, I thought we cared, about the SVD of the covariance matrix, so don't really understand how is the SVD of X relevant, can you please expand? $\endgroup$
    – m0s
    Nov 28, 2017 at 8:50
  • $\begingroup$ @m0s For PCA, we care about eigendecomposition of the covariance matrix which we usually perform by the SVD of the (centered) data matrix. $\endgroup$
    – MrDrFenner
    Jul 3, 2018 at 16:19
1
$\begingroup$

It seems to me that that a KPCA with linear kernel should be the same as the simple PCA.

The covariance matrix that you are going to get the eigenvalues from is the same:

$$ linearKPCA_{matrix} = \frac{1}{l} \sum_{j=1}^{l}K(x_{j},x_{j}) = \frac{1}{l} \sum_{j=1}^{l}x_{j}x_{j}^T = PCA_{matrix} $$

You can check with more details here.

$\endgroup$
1
  • 3
    $\begingroup$ Your answer is correct in spirit, but the formula looks confusing. KPCA works with Gram matrix $K(x_i, x_j)$, not with covariance matrix (for many nonlinear kernels it's actually impossible to compute covariance matrix as the target space has infinite dimensionality). See page 2 of the paper you cite. $\endgroup$
    – amoeba
    Jun 6, 2014 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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