Is the exponential of $-d$ a positive definite kernel for a general metric space $(X, d)$?

Question

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?

Answer 1

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).