1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for help gg. Sorry for my late reply. Reading stochastic theory takes some time. May I ask you two questions? I refer to the Wiki page of OU process and understand how to derive $cov(x_s,x_t)=\frac{\sigma^2}{2\theta}\left( \exp(-\theta |t-s|) - \exp(-\theta(t+s)) \right)$. But then the Wiki page(under the section \textit{Mathematical Properties} says, for the stationary process, the covariance of $x_s$ and $x_t$ is $\frac{\sigma^2}{2\theta}\left( \exp(-\theta |t-s|) \right)$. Can you help me understand this computation? Thanks. $\endgroup$
    – Sam Wong
    Jul 17, 2022 at 16:22
  • $\begingroup$ I still have another question. Given a random Kernel function(or under some suitable constraints, not completely random), can we always find a stochastic process whose covariance function is the Kernel function? And for my original question, how do you ‘magically’ know the Laplacian Kernel is the covariance function of a OU process? Thanks. $\endgroup$
    – Sam Wong
    Jul 17, 2022 at 16:27
  • $\begingroup$ 1) On the stationary OU process: Have a look here 2) On the existence of stochastic processes: Yes, given a kernel (with some regularity) you find a Gaussian process with this covariance function. 3) On the magically: I do not understand the question. 4) Finally: It is good practice to not ask (further) questions in comments. Best approach: Write a good question, make sure it is not answered already, and then post it. $\endgroup$
    – g g
    Jul 18, 2022 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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