2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.