How to prove that exponential kernel is positive definite?

The exponential kernel is defined by:

$$k(x,z) = e^{-\alpha\|x-z\|}$$ where $\alpha>0$, $x,z\in \Bbb{R}^d$, $\|x\|$ is the 2-norm.

The kernel matrix is defined by $K_{ij} = k(x_i,x_j)$, $i,j\in[1\ldots n]$.

How to prove that $K$ is a positive (semi-positive) definite matrix?

-
Where is the problem from? At least, we can assume $\alpha=1$. – Davide Giraudo Dec 2 '12 at 13:47
It appears in the problem set of a machine learning course. Yes, $\alpha$ can be absorbed with change of scale of $x_i$. – itsuper7 Dec 2 '12 at 15:42

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.