6
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ For the function $S(s)$ where can we include $\alpha$ $\endgroup$ – Wis Feb 9 '18 at 6:36
  • $\begingroup$ 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. $\endgroup$ – MachineEpsilon Feb 11 '18 at 3:21
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.