2
$\begingroup$

Let $(I,d)$ be an arbitrary (pseudo-)metric space. Define the function $$c(i,i') := \exp\big( - d(i,i')^2 / 2 \big)$$

Is $c$ necessarily nonnegative-definite, hence a kernel function?

$\endgroup$
3
$\begingroup$

No. A counterexample is given by the $4$-cycle graph with path distance. That is, the space consists of $4$ points $v_1,\dots,v_4$ such that $d(v_1,v_3)=d(v_2,v_4)=2$, and other nonzero distances are $1$. Let $a = e^{-1/2}$. The matrix $\exp(-d^2/2)$ is $$\begin{pmatrix} 1 & a & a^{4} & a \\ a & 1 & a & a^{4} \\ a^{4} & a & 1 & a \\ a & a^{4} & a & 1 \end{pmatrix}$$ The determinant, according to Sage, is $${\left(a^{3} + a^{2} + a - 1\right)} {\left(a^{3} - a^{2} + a + 1\right)} {\left(a^{2} + 1\right)}^{2} {\left(a + 1\right)}^{3} {\left(a - 1\right)}^{3}$$ This is negative; the only factor that needs checking is $a^{3} + a^{2} + a - 1>0$.

$\endgroup$
  • $\begingroup$ The idea to consider $C_4$ comes from the fact that it's the simplest metric space that does not embed isometrically into a Hilbert space. $\endgroup$ – user147263 Jun 6 '14 at 4:22

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.