Define a point cloud $X=\{x\_i\}\_{1\leq i\leq n}$, for $x\_i\in\mathbb R^d$. Define the Wasserstein kernel as $$W(X,Y)=\max\_{T}\frac{1}{n}\sum\_{kl}T\_{kl}\langle x\_k,y\_l \rangle$$
where $T$ is any doubly stochastic matrix.
Consider point clouds $X\_1,...X\_m$ each of size $n$ and their Gram matrix $(W(X\_i,X\_j))\_{ij}$. Is it positive semi-definite?


What we know: There always exists a permutation matrix $T$ maximizing the above.



Is the Wasserstein kernel positive definite?
It is **not** positive semi-definite.


Take $m=4, n=2, d=2$.


I define $u\_i = (\lfloor i / 2 \rfloor, i \% 2)$ for $i=0\dots3$.


I take $X\_1 = \{ u\_0, u\_1\}, X\_2 = \{u\_0, u\_2\}, X\_3 = \{u\_0, u\_3\}, X\_4 = \{u\_1, u\_2\}$


$W(X\_i, X\_j) = 0$ means that all vectors in the two sets are orthogonal. It can only happen for $\{i, j\} = \{1, 2\}$.


$W(X\_i, X\_j) = 1$ implies that either $i=j=3$ or $i=j=4$.


Hence, $$2 G = \begin{bmatrix}
 1 & 0 & 1 & 1\\
 0 & 1 & 1 & 1\\
 1 & 1 & 2 & 1\\
 1 & 1 & 1 & 2
\end{bmatrix}$$


One can easily show that $|G| = -1/16$ (see on [wolframalpha](https://www.wolframalpha.com/input/?i=determinant+of+%7B%7B1%2C+0%2C+1%2C+1%7D%2C+%7B0%2C+1%2C+1%2C+1%7D%2C+%7B1%2C+1%2C+2%2C+1%7D%2C+%7B1%2C+1%2C+1%2C+2%7D%7D)).


Hence, it must have a negative eigenvalue, which implies the kernel is not positive semi-definite.


