On sparsity, extremal structure, and monotonicity properties of Wasserstein and Gromov-Wasserstein optimal transport plans
This work provides theoretical insights into the structure of Gromov-Wasserstein distances, which is incremental for researchers in optimal transport and related fields.
The paper investigates sparsity, extremal structure, and monotonicity properties of Gromov-Wasserstein optimal transport plans, showing that under a conditionally negative semi-definite property, there exist sparse plans supported on permutations.
This note gives a self-contained overview of some important properties of the Gromov-Wasserstein (GW) distance, compared with the standard linear optimal transport (OT) framework. More specifically, I explore the following questions: are GW optimal transport plans sparse? Under what conditions are they supported on a permutation? Do they satisfy a form of cyclical monotonicity? In particular, I present the conditionally negative semi-definite property and show that, when it holds, there are GW optimal plans that are sparse and supported on a permutation.