10
$\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$
2
  • $\begingroup$ Where is the problem from? At least, we can assume $\alpha=1$. $\endgroup$ Commented Dec 2, 2012 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
    Commented Dec 2, 2012 at 15:42

1 Answer 1

8
$\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$
1
  • $\begingroup$ Good, Thank you. Hausdorff-Bernstein-Widder Theorem and interpolation theorem are so nice and powerful! $\endgroup$
    – itsuper7
    Commented Dec 3, 2012 at 3:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .