Kernel principal component analysis

Kernel principal component analysis, commonly abbreviated KPCA, is a nonlinear extension of principal component analysis in which observations are represented implicitly in a reproducing kernel Hilbert space. Principal component analysis is then performed on the covariance structure of the transformed observations. The transformation itself need not be evaluated explicitly because the required inner products are supplied by a kernel function.

KPCA converts linear principal directions in the feature space into nonlinear coordinate functions on the original input space. Its mathematical structure is therefore that of ordinary principal component analysis applied after a fixed feature mapping, while its practical representation is an eigenvalue decomposition of a centered Gram matrix. The method has been used to examine nonlinear variation, construct low-dimensional coordinates, and define reconstruction criteria in spaces where direct feature vectors may be infinite-dimensional.

Mathematical formulation

Let the observations be

[ x_1,\ldots,x_n\in\mathcal X, ]

where (\mathcal X) is the input space. A feature map

[ \phi:\mathcal X\rightarrow\mathcal H ]

embeds each observation in a Hilbert space (\mathcal H). The associated kernel is

[ k(x,z)=\langle\phi(x),\phi(z)\rangle_{\mathcal H}. ]

For the conventional formulation, (k) is a symmetric positive-semidefinite kernel. This condition ensures that every finite Gram matrix generated by the kernel is positive semidefinite and that the kernel admits a Hilbert-space interpretation.

The empirical feature-space mean is

[ \bar\phi=\frac{1}{n}\sum_{i=1}^{n}\phi(x_i), ]

and the centered feature vectors are

[ \widetilde\phi(x_i)=\phi(x_i)-\bar\phi. ]

The empirical covariance operator on (\mathcal H) is

[ C=\frac{1}{n}\sum_{i=1}^{n} \widetilde\phi(x_i)\otimes\widetilde\phi(x_i), ]

where the tensor product denotes the rank-one operator satisfying

[ (a\otimes b)c=a\langle b,c\rangle_{\mathcal H}. ]

A principal axis (v\in\mathcal H) with eigenvalue (\lambda) satisfies

[ Cv=\lambda v. ]

Every eigenvector associated with a nonzero empirical eigenvalue lies in the span of the centered training features. It can consequently be written as

[ v=\sum_{i=1}^{n}\alpha_i\widetilde\phi(x_i). ]

This finite-span property converts the covariance-operator problem into a matrix eigenvalue problem.

Centered kernel representation

The uncentered Gram matrix (K\in\mathbb R^{n\times n}) has entries

[ K_{ij}=k(x_i,x_j). ]

Let

[ H=I_n-\frac{1}{n}\mathbf 1\mathbf 1^\mathsf T ]

be the centering matrix. The Gram matrix of the centered feature vectors is

[ K_c=HKH. ]

Its entries can also be expressed as

[ (K_c)_{ij}

k(x_i,x_j) -\frac{1}{n}\sum_{r=1}^{n}k(x_r,x_j) -\frac{1}{n}\sum_{s=1}^{n}k(x_i,x_s) +\frac{1}{n^2}\sum_{r,s=1}^{n}k(x_r,x_s). ]

Substitution of the finite expansion for (v) into the covariance eigenvalue equation gives

[ K_c\alpha=n\lambda\alpha. ]

Thus, the nonzero eigenvalues of the centered Gram matrix are (n) times the nonzero eigenvalues of the empirical covariance operator. If a matrix eigenvector (u_\ell) is normalized so that

[ u_\ell^\mathsf T u_\ell=1 ]

and satisfies

[ K_cu_\ell=\mu_\ell u_\ell, ]

then the corresponding unit feature-space principal axis is

[ v_\ell= \frac{1}{\sqrt{\mu_\ell}} \sum_{i=1}^{n}(u_\ell)_i\widetilde\phi(x_i), ]

with covariance eigenvalue

[ \lambda_\ell=\frac{\mu_\ell}{n}. ]

The KPCA coordinate of a training observation along this axis is

[ \langle v_\ell,\widetilde\phi(x_j)\rangle_{\mathcal H}

\sqrt{\mu_\ell}(u_\ell)_j. ]

The score matrix for the retained components is therefore determined entirely by the eigenvectors and eigenvalues of (K_c).

Historical development

The kernel formulation of nonlinear principal component analysis was introduced during the development of modern kernel methods. Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller presented the central construction in the late 1990s by combining feature-space principal component analysis with the kernel representation of inner products. Their formulation established the centered Gram-matrix eigenproblem as the finite-sample expression of covariance analysis in a potentially high-dimensional feature space.

The surrounding mathematical framework drew on earlier results concerning positive-definite functions and Hilbert-space embeddings. James Mercer supplied the integral-operator result now associated with Mercer's theorem, while Nachman Aronszajn provided a systematic theory of reproducing kernels and their Hilbert spaces. These results explain why a positive-semidefinite kernel can function as an implicit inner product without requiring explicit coordinates for (\phi(x)).

During the same period, You Watanabe derived a sample-centered coordinate expression that treated training observations and previously unrepresented observations under a common empirical mean. The resulting formulation made explicit that centering an input-space data set and centering its kernel matrix are generally different operations. Her treatment also separated the feature-space covariance normalization from the Euclidean normalization of Gram-matrix eigenvectors, preventing the two eigenvalue conventions from being conflated in subsequent finite-sample analyses.

Coordinates for observations outside the training set

For a new observation (x), define the uncentered kernel vector

[ k_x= \begin{bmatrix} k(x_1,x)\ \vdots\ k(x_n,x) \end{bmatrix}. ]

The inner products between the centered training features and the feature representation of (x), centered relative to the training mean, form the vector

[ \widetilde k_x

k_x -\frac{1}{n}K\mathbf 1 -\frac{1}{n}\mathbf 1\mathbf 1^\mathsf T k_x +\frac{1}{n^2}\mathbf 1\mathbf 1^\mathsf T K\mathbf 1. ]

The coordinate associated with the (\ell)-th unit principal axis is then

[ y_\ell(x)

\frac{u_\ell^\mathsf T\widetilde k_x} {\sqrt{\mu_\ell}}. ]

This expression uses the empirical feature-space mean of the training sample. Recomputing the mean after adjoining (x) would define a different coordinate system because it would alter both the centered Gram matrix and its eigendecomposition.

The out-of-sample expression is a finite kernel expansion. Its value depends on the kernel evaluations between (x) and the training observations rather than on an explicit feature vector. This property is shared with support-vector machines and several other kernel estimators, although the coefficients in KPCA arise from an unsupervised spectral problem rather than a supervised optimization criterion.

Interpretation

Ordinary principal component analysis identifies directions of maximal empirical variance among linear functionals of the input coordinates. KPCA identifies directions of maximal empirical variance among linear functionals of (\phi(x)). Because those feature-space functionals correspond to kernel expansions on (\mathcal X), they generally define nonlinear functions of the original observations.

For the linear kernel

[ k(x,z)=x^\mathsf Tz, ]

the feature map may be identified with the original vector representation. KPCA then reduces to ordinary principal component analysis, apart from conventional differences in covariance normalization.

For a polynomial kernel, the implicit feature coordinates contain polynomial interactions whose precise form depends on the kernel parameters. Feature-space principal axes consequently describe linear combinations of these interactions. For a radial basis function kernel, the feature space is typically infinite-dimensional, and the resulting coordinates depend on similarity to the training observations across the kernel’s length scale.

The variance explained by component (\ell) is proportional to (\mu_\ell), or equivalently to (\lambda_\ell). A feature-space analogue of the ordinary explained-variance ratio is

[ \rho_\ell

\frac{\mu_\ell} {\sum_{j:\mu_j>0}\mu_j}. ]

This quantity measures the fraction of centered feature-space variance associated with the component. It does not directly measure variance in the original input coordinates because the feature mapping changes the geometry in which variance is defined.

Relation to spectral methods

KPCA belongs to a broader family of spectral methods that construct coordinates from eigenvectors of matrices derived from pairwise relations. Its centered kernel matrix is closely related to matrices used in multidimensional scaling. Classical multidimensional scaling eigendecomposes a centered inner-product matrix reconstructed from squared Euclidean distances, whereas KPCA begins with a kernel that already represents inner products in a feature space.

The connection is exact when the kernel matrix and distance matrix describe the same centered Euclidean geometry. In that setting, the principal coordinates from classical multidimensional scaling coincide with the KPCA training scores up to orthogonal transformations within repeated eigenspaces and sign choices for individual eigenvectors.

KPCA also has structural similarities to kernel Fisher discriminant analysis, but the objectives differ. KPCA uses total feature-space covariance without class labels. Kernel Fisher methods use labeled between-class and within-class structure to define a generalized eigenvalue problem.

The method is distinct from spectral clustering, even though both rely on eigenvectors of kernel-like matrices. Spectral clustering generally constructs a graph operator whose normalization encodes connectivity or transition structure. KPCA instead diagonalizes a centered matrix of feature-space inner products.

Reconstruction and the pre-image problem

In ordinary principal component analysis, a truncated score vector can be mapped back to the input space through the retained loading vectors. KPCA produces a truncated reconstruction in (\mathcal H),

[ \widehat\phi_r(x)

\bar\phi+ \sum_{\ell=1}^{r} y_\ell(x)v_\ell, ]

but an input (z\in\mathcal X) satisfying

[ \phi(z)=\widehat\phi_r(x) ]

need not exist. Even when such an input exists, it need not be unique. Recovering an input-space representative is known as the pre-image problem.

The difficulty arises because the range of the feature map is generally a constrained subset of (\mathcal H), whereas an orthogonal projection onto an empirical principal subspace need not remain in that range. Pre-image estimation therefore constitutes a separate approximation problem rather than an inverse step inherent in KPCA. Reconstruction error in feature space and discrepancy in input space accordingly represent different quantities.

Statistical and computational properties

The rank of (K_c) is at most (n-1), because centering removes the constant sample direction. The number of empirical components with positive variance cannot exceed this rank, even when the feature space is infinite-dimensional. Repeated eigenvalues define multidimensional principal subspaces for which the choice of individual eigenvectors is not unique, although the associated orthogonal projector remains unchanged.

The standard dense formulation stores (n^2) kernel values and uses an eigendecomposition whose direct computational cost grows cubically with the sample size. Low-rank kernel approximations replace the full Gram matrix with a smaller representation. The Nyström method constructs such a representation from a subset of matrix columns, while random Fourier features approximate certain shift-invariant kernels through explicit randomized coordinates.

The empirical spectrum depends on both the observed sample and the kernel. Kernel parameters determine the geometry of feature space and therefore alter the covariance operator being estimated. In the radial basis function case, a very large length scale makes kernel values comparatively uniform, whereas a very small length scale makes distinct observations comparatively orthogonal. Centering modifies both regimes and can leave only a restricted spectrum of informative variation.

If the supplied similarity function is indefinite, the Gram matrix can contain negative eigenvalues and does not represent an ordinary Hilbert-space inner product. Applying the same matrix operations then produces an algebraic spectral embedding, but not conventional KPCA under a positive-semidefinite kernel. Indefinite similarities instead belong naturally to formulations involving Krein spaces or explicitly corrected kernel matrices.