Relationship between PCA and KPCA

Question

The relation between PCA and KPCA seems somewhat confusing. Basically, the Kernel variant of PCA can be described as constructing the normalized kernel matrix of the data $n \times n$ (n is the number of samples), followed by eigendecomposition to extract the linear principal components. Then, KPCA can extract up to n (number of samples) nonlinear principal components.

Does this have the same effect as performing PCA on the data matrix associated with a kernel matrix, where the data matrix $X$ of kernel matrix $K$ is expressed as: $$ K = U\Sigma U^{\top} = U\Sigma^{1/2}(U\Sigma^{1/2})^{\top} = XX^{\top} $$

In other words, for $K = XX^{\top}$, the following relation should hold between PCA and KPCA: $$ KPCA(K) == PCA(X^{\top}) $$

Does the above relation hold?

Answer 1

Yes. A great reference is the original paper: Nonlinear Component Analysis as an Eigenvalue Problem - Scholkopf, et. al.

The idea is that you are boosting your vectors $x_i$ to a higher dimensional space via $\Phi(x_i)$.This gives you a covariance matrix $\bar{C}=\frac{1}{n}\sum_{i=1}^n\Phi(x_i)\Phi(x_i)^T,$ which has corresponding eigenvectors $\bar{C}V_k=\lambda_kV_k$. You now define $K(x,y):=\Phi(x)\cdot \Phi(y)$ and $K_{ij}:=K(x_i,x_j)$, so that by the rules of linear algebra, the PCA projection for $x$ looks like:

$$V^k\cdot\Phi(x)=\sum_{i=1}^na_i^kK(x_i,x),$$

where $a_i^k$ can be determined by computing the eigenvalues of $K_{ij}$. Specifically the $a_{i}^k$ are determined through requiring that $V^k=\sum_{i=1}^na_i^k\Phi(x_i)$ and $V^k\cdot V^k=1$, where the first equation restates the classical fact that the span of eigenvectors is equivalent to the span of the row/column vectors of a square positive definite matrix. Equivalently, $a^k$ are eigenvectors of the kernel matrix $K_{ij}$: $Ka^k=n\lambda \alpha^k$.