6
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Good, Thank you. Hausdorff-Bernstein-Widder Theorem and interpolation theorem are so nice and powerful! $\endgroup$ – itsuper7 Dec 3 '12 at 3:29

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.