# Prove that the squared exponential covariance is non-negative definite

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 ?

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.
• For the function $S(s)$ where can we include $\alpha$ – Wis Feb 9 '18 at 6:36
• Ah, sorry I missed that as Rasmussen and Williams assume $\alpha = 1$. Since the Fourier transform $\mathcal{F_s}$ is really just an integral, by the linearity of integration you can always pull $\alpha$ out of the function. – MachineEpsilon Feb 11 '18 at 3:21