In the field of multivariate statistics, kernel principal component analysis (kernel PCA) is an extension of principal component analysis (PCA) using techniques of kernel methods. Using a kernel, the originally linear operations of PCA are performed in a reproducing kernel Hilbert space.
Background: Linear PCA Recall that conventional PCA operates on zero-centered data; that is,
1 N ∑ i = 1 N x i = 0 {\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}\mathbf {x} _{i}=\mathbf {0} } , where x i {\displaystyle \mathbf {x} _{i}} is one of the N {\displaystyle N} multivariate observations. It operates by diagonalizing the covariance matrix,
C = 1 N ∑ i = 1 N x i x i ⊤ {\displaystyle C={\frac {1}{N}}\sum _{i=1}^{N}\mathbf {x} _{i}\mathbf {x} _{i}^{\top }}
in other words, it gives an eigendecomposition of the covariance matrix:
λ v = C v {\displaystyle \lambda \mathbf {v} =C\mathbf {v} }
which can be rewritten as
λ x i ⊤ v = x i ⊤ C v for i = 1 , … , N {\displaystyle \lambda \mathbf {x} _{i}^{\top }\mathbf {v} =\mathbf {x} _{i}^{\top }C\mathbf {v} \quad {\textrm {for}}~i=1,\ldots ,N} . (See also: Covariance matrix as a linear operator)
Introduction of the Kernel to PCA To understand the utility of kernel PCA, particularly for clustering, observe that, while N points cannot, in general, be linearly separated in d < N {\displaystyle d<N} dimensions, they can almost always be linearly separated in d ≥ N {\displaystyle d\geq N} dimensions. That is, given N points, x i {\displaystyle \mathbf {x} _{i}} , if we map them to an N-dimensional space with
Φ ( x i ) {\displaystyle \Phi (\mathbf {x} _{i})} where Φ : R d → R N {\displaystyle \Phi :\mathbb {R} ^{d}\to \mathbb {R} ^{N}} , it is easy to construct a hyperplane that divides the points into arbitrary clusters. Of course, this Φ {\displaystyle \Phi } creates linearly independent vectors, so there is no covariance on which to perform eigendecomposition explicitly as we would in linear PCA. Instead, in kernel PCA, a non-trivial, arbitrary Φ {\displaystyle \Phi } function is 'chosen' that is never calculated explicitly, allowing the possibility to use very-high-dimensional Φ {\displaystyle \Phi } 's if we never have to actually evaluate the data in that space. Since we generally try to avoid working in the Φ {\displaystyle \Phi } -space, which we will call the 'feature space', we can create the N-by-N kernel
K = k ( x , y ) = ( Φ ( x ) , Φ ( y ) ) = Φ ( x ) T Φ ( y ) {\displaystyle K=k(\mathbf {x} ,\mathbf {y} )=(\Phi (\mathbf {x} ),\Phi (\mathbf {y} ))=\Phi (\mathbf {x} )^{T}\Phi (\mathbf {y} )}
… excerpt ends here. Continue reading the full article.
