Positive-semidefinite kernel

A symmetric function $k$ is a positive-semidefinite kernel when every finite Gram matrix $(k(x_i,x_j))$ is positive semidefinite.

In the compact-domain spectral setting, a Mercer kernel is a continuous symmetric positive-semidefinite kernel on a compact space equipped with a finite full-support measure. Mercer's theorem yields nonnegative eigenvalues and an expansion $k(x,z)={\sum }_j{\lambda }_j{e}_j(x)e_j(z)$, giving features $(\sqrt{{\lambda }_j}{e}_j(x){)}_j$ in ${\ell }^2$. The finite-Gram positivity condition on arbitrary domains is more general than these spectral hypotheses; all such kernels still have a Reproducing kernel Hilbert space realization.

A real positive-semidefinite kernel satisfies $|k(x,y){|}^2\le k(x,x)k(y,y)$. This follows from positivity of its two-point kernel matrix. If a diagonal value is zero, the corresponding off-diagonal values must also vanish.

For points $x_1,\dots ,x_n$, the kernel matrix has entries $K_{ij}=k(x_i,x_j)$ and is positive semidefinite.

A feature map sends $x$ to a vector $\varphi (x)$ in a vector space with an inner product so that $k(x,y)=⟨\varphi (x),\varphi (y)⟩$.

On the finite formal span of symbols $e_x$, define $B(e_x,e_y)=k(x,y)$ and extend bilinearly. For a positive-semidefinite kernel, the null vectors of this positive semidefinite bilinear form form its radical of a bilinear form. Quotienting by that linear subspace gives an inner product space and feature map $x\mapsto [e_x]$ with $⟨[e_x],[e_y]⟩=k(x,y)$. This construction works for degenerate and zero kernels.

A random feature map is a random function $\hat{\varphi }:\mathcal{X}\to {\mathbb{R}}^q$ whose expected inner product represents a kernel:

Random Fourier features represent a translation-invariant positive-semidefinite kernel by sampling frequencies from its spectral distribution and using sine and cosine features. They replace an implicit infinite-dimensional feature map by a finite random approximation.

The Gaussian kernel is a translation-invariant positive-semidefinite kernel whose canonical feature map takes values in an infinite-dimensional vector space.

The linear kernel is the ordinary inner product on a real vector space.

For $x,z\in {\mathbb{R}}^d$, a polynomial kernel is the positive-semidefinite kernel $k(x,z)=(x^{T}z+c{)}^r$, where $r$ is a positive integer and $c\ge 0$. The case $c=0$ uses monomials of total degree $r$; $c>0$ also includes lower degrees. The feature map weights matter: listing each distinct monomial once with coefficient one generally gives a different inner product.^[ref]

For the homogeneous quadratic case in two dimensions, take the scaled quadratic feature mapThe inner product identity is explicit:The factor $\sqrt{2}$ accounts for the two equal cross terms in the square. Thus an inner product of three derived coordinates can be obtained from an inner product of the two input coordinates followed by squaring. The kernel trick uses this equality inside an algorithm; the feature map explains which nonlinear functions the algorithm can represent.

Nonnegative scalar multiples, sums, pointwise products, pointwise limits, and pullbacks of positive-semidefinite kernels are positive semidefinite whenever the displayed expressions are defined.

Suppose $k_{\tau }$ is a positive-semidefinite kernel for every $\tau$ and its diagonal entries are integrable. Positivity of each $2\times 2$ kernel matrix givesThe Cauchy-Schwarz inequality makes every entry integrable, and integrating each nonnegative finite quadratic form shows that $\int k_{\tau }d\tau$ is again a positive-semidefinite kernel.

The pointwise product of two positive-semidefinite kernels is positive semidefinite because its finite kernel matrix is the entrywise product of two positive-semidefinite matrices, to which the Schur product theorem applies.

The Laplace kernel on ${\mathbb{R}}^d$ is a translation-invariant positive-semidefinite kernel. Independent standard Cauchy random variables give its Random Fourier feature representation through their characteristic function $e^{-|t|}$.

A reproducing-kernel Hilbert space is a Hilbert space of functions in which point evaluation is continuous and satisfies $f(x)=⟨f,k(x,\cdot )⟩$.

For positive-semidefinite kernels $k_j$ with Reproducing kernel Hilbert spaces ${\mathcal{H}}_j$, the Reproducing kernel Hilbert space of $k={\sum }_j{k}_j$ consists of sums $f={\sum }_j{f}_j$, withThe minimum is attained uniquely. Indeed, in the Hilbert space direct sum $E={⨁}_j{\mathcal{H}}_j$, the tuples summing to zero form a closed subspace $N$: they are the intersection, over inputs $x$, of the kernels of the continuous maps $(f_j)\mapsto {\sum }_j{f}_j(x)$. Every affine fibre has a unique representative in $N^{\perp }$ by orthogonal decomposition by a closed subspace. The vector $(k_j(\cdot ,x){)}_j$ lies in $N^{\perp }$ and represents evaluation in the quotient; its evaluation at $y$ is ${\sum }_j{k}_j(y,x)$, identifying the positive-semidefinite kernel with $k$.

For a real-valued loss function depending only on evaluations at $x_1,\dots ,x_n$, and a positive squared-norm penalty, any minimizing tuple in a sum of reproducing-kernel Hilbert spaces has the formwith the same coefficient vector for every component. The tuple must be the unique minimum-norm decomposition of its sum. Apply the representer theorem to that sum and note that the displayed tuple has total squared norm ${\sum }_j{\hat{\alpha }}^T{K}_j\hat{\alpha }={\hat{\alpha }}^T({\sum }_j{K}_j)\hat{\alpha }$, exactly the norm of the sum. This argument is conditional on existence of a minimizer; arbitrary loss functions need not attain their infimum.

The reproducing property is $f(x)=⟨f,k(x,\cdot ){⟩}_{\mathcal{H}}$; it turns point evaluation into an inner product with a kernel section.

The representer theorem reduces regularized optimization over a reproducing-kernel Hilbert space to the span of kernel sections at the observed points.

A kernel method represents data through a positive-semidefinite kernel, allowing algorithms to use inner products in an implicit feature map.

Kernel ridge regression minimizes empirical squared error plus the squared norm in a Reproducing kernel Hilbert space. The representer theorem reduces it to ridge regression with the kernel matrix as its feature Gram matrix.

For the unscaled objective ${\sum }_i(Y_i-f(x_i){)}^2+\lambda \Vert f{\Vert }_{\mathcal{H}}^2$, the kernel-ridge hat matrix is $H=K(K+\lambda I{)}^{-1}$. Its prediction variance is ${\sigma }^2\mathrm{tr}(H^2)/n$. For eigenvalues $d_i\ge 0$, use $d_i^2/(d_i+\lambda {)}^2\le \min \{d_i/(4\lambda ),1\}$ and ${\lambda }^2{d}_i/(d_i+\lambda {)}^2\le \lambda /4$ to bound the variance and the squared bias. The latter also uses the reproducing property and Bessel inequality, and does not require invertibility of $K$.

For kernel matrix $K$ and objective normalized as $n^{-1}\Vert Y-f{\Vert }_2^2+\lambda \Vert f{\Vert }_{\mathcal{H}}^2$, the fitted values are $H_{\lambda }Y$, where

Every positive-semidefinite kernel $k$ has a Hilbert-space feature map $\varphi$ satisfying $k(x,y)=⟨\varphi (x),\varphi (y)⟩$, and determines a unique reproducing-kernel Hilbert space.

For feature vectors $\varphi (x_i)$, the empirical uncentered kernel covariance operator is

The kernel trick evaluates inner products of feature map outputs through $k(x,z)=⟨\varphi (x),\varphi (z)⟩$ without explicitly constructing those vectors. An algorithm expressed entirely through these inner products can therefore operate on nonlinear derived coordinates using only evaluations of a positive-semidefinite kernel on the original inputs. A classifier linear in the derived coordinates can have a nonlinear boundary in the original coordinates.

The polynomial kernel gives a finite, fully visible example: $k(x,z)=(x^{T}z{)}^2$ corresponds to $\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2{)}^T$. The XOR separation by a product feature below makes the interaction coordinate $x_1{x}_2$ useful, while dual prediction with a kernel shows how to predict without calculating it explicitly.

An arbitrary score called a similarity need not be a positive-semidefinite kernel. Symmetry alone, even with nonnegative entries, is insufficient: the symmetric matrixhas $a^{T}Sa=-2$ for $a=(1,-1{)}^T$, so it cannot be a Gram matrix of real inner products. A positive-semidefinite kernel requires a positive semidefinite matrix for every finite choice of inputs, not just the observed training data.^[ref] The existing Moore-Aronszajn theorem connects this requirement to a Reproducing kernel Hilbert space; this example needs only finite linear algebra.

Give the four corners of the square the exclusive or labels: $+1$ when the input signs differ and $-1$ when they agree. In the following order,No affine function $g(x)=a_1{x}_1+a_2{x}_2+b$ has the required strictly positive scores at $p_2,p_3$ and strictly negative scores at $p_1,p_4$: both pairs have midpoint zero, so $g(p_2)+g(p_3)=2b=g(p_1)+g(p_4)$ would have to be both positive and negative. This also rules out perfect classification by a single threshold with a consistent tie rule.

Under the polynomial kernel's quadratic feature map, the two classes become two distinct vectors:The hyperplane ${\varphi }_2=0$ separates them. With $w=(0,-1/\sqrt{2},0{)}^T$ and $b=0$, the score and classifier areAll four signed scores $y_{i}f(p_i)$ equal one. In the input plane the boundary is $x_1{x}_2=0$, the union of the coordinate axes; in the derived coordinates it is a single hyperplane. The feature map identifies opposite corners, which is harmless for these labels because opposite corners belong to the same class. A fixed feature map would not separate labels that disagree at identical mapped vectors.

If the weight vector lies in the linear span of the training feature map outputs, write $w={\sum }_i{\beta }_i\varphi (p_i)$. ThenThis is a dual representation: coefficients weight training examples rather than feature coordinates. They need not be positive, and need not be unique when the kernel matrix is singular. Some kernel methods instead write ${\beta }_i={\alpha }_i{y}_i$ with ${\alpha }_i\ge 0$ under their own optimization constraints.^[ref] The formula is an algebraic conversion for a weight vector in this linear span, not a claim about every possible weight vector. The representer theorem gives a broader reason this form appears in regularized kernel methods.

For the XOR separation by a product feature, let $\Phi$ have rows $\varphi (p_i{)}^T$. The Gram matrix of those rows, equivalently the kernel matrix, isIts eigenvalues are $8,8,0,0$, so it is a positive semidefinite matrix of rank two, not an invertible matrix. More generally, for any real coefficient vector $a$ and any finite set of inputs,This proves the positive-semidefinite kernel condition for the displayed polynomial kernel on all of ${\mathbb{R}}^2$, rather than checking only this square.

Here $Ky=8y$, so the explicit choice $\beta =y/8$ gives $K\beta =y$ and ${\Phi }^T\beta =w$. ConsequentlyFor the new input $z=(1,1/2)$, the four polynomial kernel evaluations are $(9/4,1/4,1/4,9/4{)}^T$. Their weighted sum is $-1/2$, and the sign function predicts $-1$. No explicit feature map is needed for this calculation. These coefficients were constructed to reproduce the chosen separator; no fitting algorithm or generalization guarantee is being asserted.

For $d$ input coordinates, the homogeneous quadratic polynomial kernel has a weighted quadratic feature map with $D=d(d+1)/2$ distinct monomials. Computing an inner product of already stored mapped vectors costs $O(D)$ arithmetic operations, whereas $(x^{T}z{)}^2$ costs $O(d)$ using the input vectors. Here $O$ denotes big O notation. Higher fixed degrees can make the dimension gap much larger.

Sample count still matters. With $n$ training examples, materializing a dense kernel matrix stores $n^2$ numbers and requires $n(n+1)/2$ distinct evaluations using symmetry. A dense direct solve for kernel ridge regression typically takes $O(n^3)$ operations after constructing the kernel matrix, while a dual prediction with $m$ nonzero coefficients uses $m$ kernel evaluations. Explicit finite feature maps can be preferable when $D$ is small relative to $n$, and a stored primal weight vector can make prediction depend on $D$ rather than on $n$. The kernel trick by Ryan Giordano (sections Ridge regression and The polynomial kernel) explains the change from feature-coordinate equations to training-example equations; neither representation is universally faster.

The kernel trick saves explicit feature construction when the positive-semidefinite kernel is economical to evaluate; it does not remove the cost of optimization, choose a useful positive-semidefinite kernel, or establish generalization. Random Fourier features illustrate a different tradeoff: replacing the exact Gaussian kernel with a finite approximate feature map can reduce dependence on the sample count while introducing approximation error.

Kernel principal component analysis diagonalizes a centered kernel matrix to perform principal component analysis in an implicit feature space.

If a stationary Gaussian process has covariance spectral density $\hat{K}$, its reproducing-kernel Hilbert space has normon the functions for which this integral is finite.