Can a pseudo-metric yield a valid kernel?

Question

Disclaimer: This question is somewhat related to: Generalized RBF Kernels. I apologize if this has too much overlap.

---

Say we have some distance $d(x,x')$, where $x$ is from some set $X$.

$d(x,x')$ may be a metric, that is, satisfy conditions: $$d(x,x')\geq 0$$ $$d(x,x')=d(x',x)$$ $$d(x,x')=0 \iff x=x'$$ $$d(x,x')\leq d(x,x'') + d(x'',x')$$

or a pseudo-metric (i.e., $d(x,x')$ can be zero even if $x$ and $x'$ are not identical).

And we have a kernel derived from $d(x,x')$:

$$k(x,x')= -d(x,x')^\beta ~~~\text{with}~~~ \beta \in [0,2]$$

Haasdonk and Bahlman (Learning with Distance Substitution Kernels, 2004, PDF) say in Corollary 1 that

Non-Metricity Prevents Definiteness.

That is, if $d(x,x')$ is not metric, $k(x,x')$ cannot be Conditionally Positive Semi-Definite (CPSD) (see the PDF for a definition).

My question is:

Does that imply that only actual metrics (and not pseudo-metrics) can yield CPSD $k$? Or do they just not distinguish between metric/pseudo-metric?

Answer 1

Does that imply that only actual metrics (and not pseudo-metrics) can yield CPSD $k$? Or do they just not distinguish between metric/pseudo-metric?

The latter. Here's why:

Suppose we have a pseudometric $d(x,x')$. Then $d(x,x') + \alpha ||x-x'||^2$ is a metric for all $\alpha > 0$ (here $||\cdot||$ is the Euclidean norm - we could use any other true metric as well). So the associated kernel $k_\alpha$ is CPSD for all $\alpha > 0$. The question is whether it is also CPSD for $\alpha = 0$?

The answer is yes. Following the notation in your PDF: given any $c$ we have $c^T K_\alpha c \geq 0$ for all $\alpha > 0$. It is clear that $K_\alpha$ is a continuous function of $\alpha$ by its definition in your original post. So we can take the limit $\alpha \rightarrow 0$ and the inequality will still hold. Therefore the inequality holds for all $c$ at $\alpha = 0$ and we have a CPSD kernel.