1
$\begingroup$

Say a Euclidean distance function $d$ is given as: $d(x, y) = \Sigma(x_i - y_i)^2$.

How do I prove it is a valid kernel?

I know this: $d(x, y) = \Sigma(x_i - y_i)^2 = \Sigma(x_i^2 + y_i^2 - 2x_iy_i) = \langle x, x\rangle + \langle y, y\rangle - 2\langle x, y\rangle$

However, how do i prove that the difference of two kernels in this case is a valid kernel?

$\endgroup$
  • $\begingroup$ what do you mean by "valid kernel"? $\endgroup$ – utobi Dec 5 '16 at 8:04
  • 1
    $\begingroup$ that the function is symmetric and positive semidefinite $\endgroup$ – lucifer1190 Dec 5 '16 at 8:52
1
$\begingroup$

Your (squared Euclidean) distance function $d(x,y) = \sum(x_i - y_i)^2$ is quadratic and therefore $d(x,y) \geq 0 \,\, \forall x,y \in \mathbb{R}$, i.e. your kernel is positive definite. The second necessary condition for a valid kernel is symmetry, $d(x,y) = d(y,x)$, which is also fulfilled in your case.

$\endgroup$
  • $\begingroup$ As @ZeouHu has pointed out, this is incorrect $\endgroup$ – user20160 Oct 12 '19 at 17:27
0
$\begingroup$

Euclidean distance is NOT a kernel. @foo42 's answer is wrong. The Gram matrix K for euclidean distance is not positive (semi)definite, thus not satisfying Mercer's condition.

$\endgroup$
  • 1
    $\begingroup$ Welcome to the site. You're absolutely correct that Euclidean distance isn't a valid kernel function. We're generally looking for detailed answers; you could improve this post by elaborating on Mercer's condition and why Euclidean distance doesn't satisfy it. $\endgroup$ – user20160 Oct 12 '19 at 17:28

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.