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 ? 
 A: 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.
A: 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.
