Mathematical Statistics – Prove the Validity of Laplacian Kernel

Question

By a valid kernel, we mean the Gram matrix induced by it is positive semi-definite (and symmetric).

Let $K(x,y)=\exp(-\lambda \|x-y \|)$, where $\lambda >0.$ We say $K$ is a Laplacian kernel.

I know the exponential of a valid kernel is still a valid kernel. But unfortunately, $K_1(x,y)=\|x-y \|$ is not a valid kernel and my strategy is not working.

I have googled a lot and found a solution involving Fourier transform and reproducing kernel Hilbert spaces(abbr. RKHS). But I am new to this area and not really familiar with RKHS. I wonder if there is an elementary way to prove this. Many thanks.

Answer 1

This depends a lot on what you consider as "elementary". There are three ways I am aware of to establish positive definiteness which avoid Fourier transform.

1. You find the first approach in this answer to a more general question. My (partial) answer to the question establishes equivalence to your problem at least in dimension one. The solution is intricate but it only requires some basic facts about positive definite matrices.
2. If you are willing to go down the RKHS route somewhat, there is a nice and rather elementary (say undergrad maths elementary) solution in lecture notes by Schaback, Chapter 2.11 This derives the Laplacian Kernel from the reproducing property of Sobolev space and requires only partial integration and elementary ordinary differential equations.
3. Finally, if you are into stochastic processes and consider well-known facts about those as "elementary", just observe that the Laplacian Kernel is the covariance function of an Ornstein-Uhlenbeck process. Of course, covariance functions have to be positive definite.