# Is the Wasserstein kernel positive definite?

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.