Positive-Definite Covariance Kernels

Covariance Kernels and Finite Gram Matrices

A covariance function assigns a covariance to every pair of inputs. But arbitrary pairwise numbers need not be compatible with a joint distribution: for any finite collection of inputs, the resulting covariance matrix must be positive semidefinite. This condition is both a practical test—one failed finite test rules out a proposed covariance—and the central validity criterion for Gaussian-process covariance kernels.

Let \(T\) be an input set and let \((X_t)_{t\in T}\) be a real-valued process on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with \(\mathbb{E}[X_t^2]<\infty\) for every \(t\). Its mean function is \(m(t)=\mathbb{E}[X_t]\), and its covariance kernel is \(K(s,t)=\operatorname{Cov}(X_s,X_t)\). For any finite list of inputs \(t_1,\ldots,t_n\), the Gram matrix of a function \(K\) on that list is the matrix with entries \(K(t_i,t_j)\). Repeated inputs are allowed, and \(n\) is any positive integer.

The distinction between “every finite set” and “a particular finite set” matters. A negative quadratic form for even one finite set proves that \(K\) cannot be a covariance kernel. Conversely, checking one or several finite sets verifies the condition only on those sets; it does not establish positivity on all of \(T\).

Proof. First suppose \(K\) is the covariance kernel of a process with finite second moments. For any finite inputs and real coefficients, the quadratic form is $$ \sum_{i,j=1}^{n}c_i c_j K(t_i,t_j) =\operatorname{Var}\left(\sum_{i=1}^{n}c_iX_{t_i}\right)\geq 0. $$ Covariance is symmetric, so \(K(t_i,t_j)=K(t_j,t_i)\). This proves necessity, including when the variance is zero.

For sufficiency, suppose \(K\) is symmetric and positive semidefinite. For every finite list of inputs, its Gram matrix is a symmetric positive-semidefinite matrix. By finite-dimensional spectral decomposition, it is the covariance matrix of a possibly singular Gaussian vector; adding the selected values of \(m\) gives the required mean vector. If a finite list is reduced to a sublist, the Gaussian distribution on the sublist has the corresponding subvector mean and covariance, so the finite-dimensional distributions are consistent. The standard Kolmogorov extension theorem then gives a process with these finite-dimensional distributions. Its covariance at \(s,t\) is \(K(s,t)\), as specified by the two-coordinate distribution. The extension theorem is a standard result; its proof is beyond this tutorial. \(\square\)

Worked Gram-Matrix Tests

Two Further Standard Kernels

The squared-exponential, or Gaussian, kernel on \(\mathbb{R}\) is \(K(x,y)=\exp(-(x-y)^2/(2\ell^2))\), where \(\ell>0\) is a length scale. Positivity follows from a feature expansion, which expresses the quadratic form as a sum of squares. Indeed, $$ K(x,y)=e^{-x^2/(2\ell^2)}e^{-y^2/(2\ell^2)} \sum_{r=0}^{\infty}\frac{x^r y^r}{\ell^{2r}r!}. $$ For any finite inputs and coefficients, substituting this series into the quadratic form gives $$ \sum_{r=0}^{\infty}\frac{1}{\ell^{2r}r!} \left(\sum_i c_i e^{-x_i^2/(2\ell^2)}x_i^r\right)^2\geq 0. $$ The series identity is the exponential power series, and the finite sums over \(i,j\) can be interchanged with it. Each term is nonnegative, so the kernel is positive semidefinite.

Another standard example is the exponential kernel \(K(x,y)=e^{-a|x-y|}\) on \(\mathbb{R}\), where \(a>0\). To verify its Gram matrices, sort any finite list of distinct inputs as \(x_1<\cdots<x_n\), and set \(r_i=e^{-a(x_i-x_{i-1})}\) for \(i=2,\ldots,n\). Each \(r_i\) lies in \((0,1)\). Let \(\varepsilon_1,\ldots,\varepsilon_n\) be independent standard normal variables, and define \(Z_1=\varepsilon_1\) and \(Z_i=r_iZ_{i-1}+\sqrt{1-r_i^2}\,\varepsilon_i\). Inductively, \(\operatorname{Var}(Z_1)=1\) and \(\operatorname{Var}(Z_i)=r_i^2+(1-r_i^2)=1\). For \(j<i\), independence of \(\varepsilon_i\) from the earlier variables gives \(\operatorname{Cov}(Z_i,Z_j)=r_i\operatorname{Cov}(Z_{i-1},Z_j)\). Iterating yields \(\operatorname{Cov}(Z_i,Z_j)=\prod_{k=j+1}^{i}r_k=e^{-a(x_i-x_j)}\). Thus the Gram matrix is a covariance matrix and is positive semidefinite. If an input is repeated, its repeated row and column simply duplicate a coordinate, preserving nonnegativity of the quadratic form.

Rules for Building Kernels

Proof. Fix any finite list of inputs and any coefficient vector. The quadratic form for the sum is the sum of the two nonnegative quadratic forms; multiplying a quadratic form by \(b\geq0\) also preserves nonnegativity. For the product, let \(A\) and \(B\) be the two Gram matrices on the chosen inputs. By finite-dimensional spectral decomposition, each positive-semidefinite matrix is a Gram matrix: there are vectors \(u_i\) and \(v_i\) such that \(A_{ij}=\langle u_i,u_j\rangle\) and \(B_{ij}=\langle v_i,v_j\rangle\). The entrywise product has entries \(A_{ij}B_{ij}=\langle u_i,u_j\rangle\langle v_i,v_j\rangle=\langle u_i\otimes v_i,u_j\otimes v_j\rangle\). It is therefore a Gram matrix of the vectors \(u_i\otimes v_i\), and its quadratic form is the squared norm \(\|\sum_i c_i(u_i\otimes v_i)\|^2\geq0\). Since the finite inputs were arbitrary, all three constructions give positive-semidefinite kernels. \(\square\)

These rules justify useful constructions without repeating a full kernel proof. For instance, adding a nonnegative constant kernel to a known kernel remains valid, and multiplying two valid kernels pointwise remains valid. A negative scale is not covered: even \(K(x,y)=1\), which has nonnegative quadratic form, becomes invalid when multiplied by \(-1\) on a one-point set.

What a Finite Test Can and Cannot Tell You

For a proposed function, the basic workflow is to check symmetry, choose finite inputs, form every Gram entry, and test the quadratic form or an equivalent matrix criterion. A negative diagonal entry already disproves positivity by choosing a coefficient vector supported at that single input. More generally, any coefficient vector with a negative quadratic form is a certificate of failure. A positive determinant alone is not a general test for positive semidefiniteness: all eigenvalues must be nonnegative, or another valid positive-semidefiniteness criterion must be used.

Common pitfall. Checking only that \(K(t,t)\geq0\) for every input is not enough. The invalid proposal \(1-|x-y|\) has \(K(x,x)=1\) for every \(x\), yet its Gram matrix on \(0,1,3\) has quadratic form \(-2\) for coefficients \((1,0,1)\). The diagonal tests individual variances; off-diagonal covariances must also be jointly compatible. Also, a zero quadratic form does not imply failure: positive semidefinite permits equality for nonzero coefficients, as the linear kernel example demonstrates.