How to prove that a kernel is positive definite?

Question

For example, how to prove $\forall(x,y)\in R^N\times R^N,K(x,y) = \displaystyle\frac{1}{1+\frac{||x - y||^2}{{\sigma}^2}}\\$ where $\sigma > 0$ is a parameter, is positive definite? I have tried to construct the target kernel base on some negative definite kernel, such as the square distance $||x-y||^2$, but doesn't seems to work.

Answer 1

Here is a simple trick that relies only on elementary ideas.

First, we use the observation that for $t>0$ \begin{equation*} \exp(-t\|x-y\|^2) = \exp(-t\|x\|^2)\exp(2t\langle x, y\rangle)\exp(-t\|y\|^2), \end{equation*} which is clearly positive definite (use $\langle x,y\rangle^k$ is pd for $k\ge0$).

Now, just use the integral \begin{equation*} \frac{1}{1+\|x-y\|^2} = \int_0^\infty e^{-t(1+\|x-y\|^2)}dt, \end{equation*} which is basically just a nonnegative sum of positive definite functions, hence itself positive definite.

Answer 2

Schoenberg (Ann. of Math. 39 (1938), 811-841) observed that if $f(t)$ is a completely monotonic function, then the radial kernel $K(x,y)=f(\|x-y\|^2)$ is positive definite on any Hilbert space. Since $$ f(t):=\frac{1}{1+\frac{t}{\sigma^2}} $$ is completely monotonic, the result follows.

Added. Schoenberg's proof relies on the Hausdorff-Bernstein-Widder theorem and the fact that the Gaussian kernel $\exp(-\|x-y\|^2)$ is positive definite. Using these two facts, the proof is immediate.

For a modern account, see Theorem 7.13 in Wendland: Scattered Data Approximation (Cambridge University Press, 2005).