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.
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).
Hence, it must have a negative eigenvalue, which implies the kernel is not positive semi-definite.
