How to prove that exponential kernel is positive definite?

Solution 1:

The radial basis function $\phi(y) = \exp(-\alpha\sqrt{y})$ is completely monotone on $[0,\infty)$. Hence, by Schoenberg's interpolation theorem (see chapter 15 of A Course in Approximation Theory by Cheney and Light or sec. 2.5 of this book chapter, for instance), $\phi(\|\cdot\|^2)$ is strictly positive definite. Therefore $k(x,z)=\phi(\|x-z\|^2)$ is a kernel and $K$ is positive definite when the data points $x_1,\ldots,x_n$ are distinct (or positive semidefinite otherwise).

Alternatively, $K$ may be viewed as the covariance matrix for two Ornstein-Uhlenbeck processes. Hence it is positive semidefinite.