2
$\begingroup$

Let $d(\cdot, \cdot)$ be a distance metric on some space (not necessarily Euclidean) $\mathcal{X}$. Is it true that $$ K(x, y) := \exp(-d(x, y)) $$ always defines a positive definite kernel? If not, are there certain conditions on $d(\cdot, \cdot)$ under which the result is true?

$\endgroup$
2
$\begingroup$

Remark: in this subject, "positive definite" typically means "positive semidefinite" (Wikipedia) and I treat it as such. One does not expect the matrix $\exp(-d(x_i, x_j))$ to be strictly positive definite since some $x_i$ could be repeated.

Counterexample

Consider the 3-dimensional space $\ell_\infty^3$, i.e., the norm is $\|(x, y, z)\| = \max(|x|, |y|, |z|)$. Let $\mathcal X$ be the five-point subset of $\ell_\infty^3$, the coordinates of each point being a row of the matrix $$ A = \frac{1}{10} \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & -1 \\ 1 & 1 & 0 \\ 1 & -1 & 0 \\ -1 & 1 & 0 \end{pmatrix} $$ The distance matrix of this space is $$ D = \frac{1}{10} \begin{pmatrix} 0 & 2 & 1 & 1 & 1 \\ 2 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 2 & 2 \\ 1 & 1 & 2 & 0 & 2 \\ 1 & 1 & 2 & 2 & 0 \end{pmatrix} $$ Applying the function $t\mapsto \exp(-t)$ to each element of $D$, we get a matrix $B$ which is not positive semidefinite. Specifically, the vector $v = (3, 3, -2, -2, -2)$ satisfies $$ vBv^T = 30 + 42e^{-1/5} - 72e^{-1/10} < 0 $$

Sufficient condition

The kernel $\exp(-\lambda d)$ is positive semidefinite for all $\lambda>0$ if and only if $d$ is a a kernel of conditionally negative type, see Transforming a distance function to a kernel. In the article linked there, Schoenberg proved that a metric space admits an isometric embedding into a Hilbert space if and only if $d^{2}$ is a kernel of conditionally negative type.

Conclusion: if $(X, d)$ is a metric space such that its "snowflake" $(X, d^{1/2})$ admits an isometric embedding into a Hilbert space, then $\exp(-d)$ is a positive semidefinite kernel. Examples of such spaces are: Hilbert space itself, $L^1$, and of course any subsets of those.

This motivated my counterexample above: $\ell_\infty^3$ is one of the simplest spaces that do not embed into $L^1$.

A contemporary source on this subject is Naor's ICM talk on $L^1$ embeddings (its main subject is the Heisenberg group, but the introduction gives an overview of the situation).

$\endgroup$

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.