Search papers, labs, and topics across Lattice.
This paper investigates the sparsity, permutation support, and cyclical monotonicity properties of Gromov-Wasserstein (GW) optimal transport plans, contrasting them with standard optimal transport (OT). It demonstrates that under the conditionally negative semi-definite property, GW optimal plans can be both sparse and supported on a permutation. This finding provides insights into the structural characteristics of GW transport, potentially leading to more efficient computational methods and a deeper understanding of its applications.
Gromov-Wasserstein optimal transport plans can be sparse and permutation-supported under certain conditions, challenging the intuition that they are always dense.
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.
