Prove that the squared exponential covariance is non-negative definite

Question

Consider a covariance function of the form $$K_{i,j}=\alpha\times exp(-0.5 (x_i-x_j)^2/l^2)$$

This is a very common function used in Gaussian processes. How to show that this covariance is non-negative definite ?

Answer 1

I am not an expert but I'll sketch a standard argument which is explained in more detail in Rasmussen and Williams, Chapter 4 Section 2.1 (that book has answered a ton of my question about GPs). So we are working with the squared exponential function right? We have: $$K_{i,j}= \alpha \cdot \mathrm{exp}(\frac{-(x_i-x_j)^2}{2\ell^2}) = \alpha \cdot \mathrm{exp}(\frac{-(|x_i-x_j|)^2}{2\ell^2})$$

Since kernel can be written as a function of $|x_i-x_j|$, it is stationary (isotropic, even). Since it is stationary, the trick is we can apply Bochner's theorem to $K_{i,j}$. In this case, showing positive semidefiniteness of the square exponential reduces to finding a suitable function $S(s)$ which we can take the Fourier transform $\mathcal{F}_s$ such that $\mathcal{F}_s(S(s))=K_{i,j}$. Now the Fourier transform of a Gaussian is another Gaussian, so the $S(s)$ function that we are looking for turns out to be $$ S(s) = \alpha (2\pi \ell^2)^{D/2} \mathrm{exp}(−2\pi^2 \ell^2s^2). $$ If you calculate the Fourier transform of this function you will get your kernel, thus showing it's positive semidefinite. I'm sorry if that's too terse, but I can try to derive more details if that helps.

Answer 2

There are also 3 more proofs here: How to prove that the radial basis function is a kernel?

Note that the "squared exponential" kernel is also called a "radial basis function" (RBF) kernel and a "Gaussian" kernel.