Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Good, Thank you. Hausdorff-Bernstein-Widder Theorem and interpolation theorem are so nice and powerful! –  itsuper7 Dec 3 '12 at 3:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.