# How to prove that the radial basis function is a kernel?

How to prove that the radial basis function $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ is a kernel? As far as I understand, in order to prove this we have to prove either of the following:

1. For any set of vectors $x_1, x_2, ..., x_n$ matrix $K(x_1, x_2, ..., x_n)$ = $(k(x_i, x_j))_{n \times n}$ is positive semidefinite.

2. A mapping $\Phi$ can be presented such as $k(x, y)$ = $\langle\Phi(x), \Phi(y)\rangle$.

Any help?

-

Zen used method 1. Here is method 2: Map $x$ to a spherically symmetric Gaussian distribution centered at $x$ in the Hilbert space $L^2$. The standard deviation and a constant factor have to be tweaked for this to work exactly. For example, in one dimension,

$$\int_{-\infty}^\infty \frac{\exp[-(x-z)^2/(2\sigma^2)]}{\sqrt{2 \pi} \sigma} \frac{\exp[-(y-z)^2/(2 \sigma^2)}{\sqrt{2 \pi} \sigma} dz = \frac{\exp [-(x-y)^2/(4 \sigma^2)]}{2 \sqrt \pi \sigma}.$$

So, use a standard deviation of $\sigma/\sqrt 2$ and scale the Gaussian distribution to get $k(x,y) = \langle \Phi(x), \Phi(y)\rangle$. This last rescaling occurs because the $L^2$ norm of a normal distribution is not $1$ in general.

-
(+1) Good answer. – cardinal Sep 3 '12 at 23:35
(+1) Nice, Douglas! – Zen Sep 3 '12 at 23:47
That's team work! SE! SE! SE! SE! – Zen Sep 4 '12 at 1:47
@Zen, Douglas Zare: thank you for your great answers. How am I supposed to select the official answer now? – Leo Sep 4 '12 at 22:03
Please, give it to Douglas. The poor guy has just 1624 rep points ;-) – Zen Sep 4 '12 at 23:48

I will use method 1. Check Douglas Zare answer for a proof using method 2.

I will prove the case when $x,y$ are real numbers, so $k(x,y)=\exp(-(x-y)^2/2\sigma^2)$. The general case follows mutatis mutandis from the same argument, and is worth doing.

Without loss of generality, suppose that $\sigma^2=1$.

Write $k(x,y)=h(x-y)$, where $$h(t)=\exp\left(-\frac{t^2}{2}\right)=\mathrm{E}\left[e^{itZ}\right]$$ is the characteristic function of a random variable $Z$ with $N(0,1)$ distribution.

For real numbers $x_1,\dots,x_n$ and $a_1,\dots,a_n$, we have $$\sum_{j,k=1}^n a_j\,a_k\,h(x_j-x_k) = \sum_{j,k=1}^n a_j\,a_k\,\mathrm{E} \left[ e^{i(x_j-x_k)Z}\right] = \mathrm{E} \left[ \sum_{j,k=1}^n a_j\,e^{i x_j Z}\,a_k\,e^{-i x_k Z}\right] = \mathrm{E}\left[ \left| \sum_{j=1}^n a_j\,e^{i x_j Z}\right|^2\right] \geq 0 \, ,$$ which entails that $k$ is a positive semidefinite function, aka a kernel.

To understand this result in greater generality, check out Bochner's Theorem: http://en.wikipedia.org/wiki/Positive-definite_function

-
This is a good start, in the right direction, with two caveats: (a) $h(t)$ is not equal to the expectation shown (check the sign in the exponent) and (b) this appears to restrict attention to the case where $x$ and $y$ are scalars and not vectors. I've upvoted in the meantime, because the exposition is nice and clean and I'm sure you'll quickly plug these small gaps. :-) – cardinal Sep 3 '12 at 23:21
Tks! I'm in a hurry here. :-) – Zen Sep 3 '12 at 23:42