How do I prove that Euclidean Distance Function is a valid kernel? 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?
 A: 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.
A: A kernel $K: \cal{X}\times\cal{X}\to \mathbb{R}$ is "valid" if it can be written as the inner product of corresponding vectors in some "feature space" $\cal{F}$.
More formally, define a feature mapping $\Psi: \cal{X} \to \cal{F}$. A kernel $K$ is valid if $\exists \Psi: \cal{X} \to \cal{F}$ such that $\forall x, \tilde{x} \in \cal{X}$,
$$\langle \Psi(x), \Psi(\tilde{x})\rangle=K(x, \tilde{x})$$.
In practice this is difficult to check directly. Hence, Mercer's Theorem gives us a necessary and sufficient condition for checking if a kernel is valid:

Mercer's theorem: A symmetric function $K: \cal{X}\times\cal{X}\to \mathbb{R}$ is a valid kernel iff for every integer $m\ge1$ and every vector $v_1, ..., v_m \in \cal{X}$, the "Gram matrix" $G \in \mathbb{R}^{m\times m}$ given by
$$
G_{i,j} = K(v_i, v_j) \quad \forall i, j \in [m]
$$
is positive semi-definite (i.e., $\forall y \in \mathbb{R}^m, y^\top Gy \ge 0$).

So, if a kernel is not valid, it suffices to find an $m\ge 1$ and some set of vectors $v_1, ..., v_m \in \cal{X}$ such that $G$ is not positive semi-definite.
We can see that $K(x, \tilde{x}) = ||x-\tilde{x}||^2_2$ is not a valid kernel by setting $m=2$: For any arbitrary pair of vectors $v_1, v_2 \in \cal{X}$,
$$
G = 
\begin{bmatrix}
0 & ||v_1-v_2||^2_2 \\
||v_1-v_2||^2_2 & 0
\end{bmatrix} = 
\begin{bmatrix}
0 & c \\
c & 0
\end{bmatrix}, c \ge 0
$$
To check if $G$ is positive semi-definite, let $y \in \mathbb{R}^2$ be arbitrary, where $y^\top = [y_1 \quad y_2]$. Then $y^\top G y = 2c(y_1 y_2)$. Hence if $y_1 >0$ and $y_2<0$, $y^\top G y <0$. Therefore, G is not necessarily positive semi-definite. By Mercer's Theorem, $K$ is not a valid kernel.
A: 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.
