Advances in Gromov–Wasserstein optimal transport: linearization, multi-marginal generalization, barycenters and transfer operators

Over the past few decades, optimal transport (OT) has progressively shifted into the focus of modern applied mathematics. Central to OT are various optimization problems, namely transport problems, whose solutions provide a divergence and an inner alignment between given input measures. The nature of the divergence and alignment is decided by some underlying cost that is sought to be minimized. The recent popularity of OT is in particular due to the vast amount of data that can be mathematically modelled by measures, the possibility to choose costs which are tailored to the desired task, fast approximate solvers that allow the handling of large scale problems and its amenability for further generalization. In this cumulative thesis, we develop theory, algorithms and applications of generalized optimal transport models with a primary focus on the Gromov–Wasserstein (GW) transport problem. Figuratively, this transport problem offers a relaxed way of finding a correspondence that retains the geometry between given inputs, and evaluating how far they are from being isometric. After briefly introducing various transport problems and fixing the notation, we proceed with a presentation of our main results which are divided into several topics. In the first part of this thesis, we study multi-marginal transport problems which essentially allow for a simultaneous alignment and comparison of an arbitrary number of inputs. We consider a multi-marginal Kantorovich problem in an unbalanced context which leads us to the so-called unbalanced multi-marginal OT. The induced multi-marginal transport plan between the measures seeks to minimize a given cost function on the product space. Due to the unbalanced setting, this formulation is robust to noise and outliers. We extend a popular approximate solver, namely the Sinkhorn algorithm, to this generalized context. In particular, we show that the algorithm converges under mild assumptions. The novel transport problem can be leveraged to characterize unbalanced OT barycenters which are generalized Fréchet means with respect to the unbalanced Kantorovich divergence. For the barycenter case, the proposed generalized Sinkhorn algorithm can be implemented efficiently. Then, we turn our attention to generalizing the GW transport problem in a similar manner, i.e. we define an (unbalanced) multi-marginal variant of the GW transport problem. Based on the associated bi-convex relaxation, which we show to be tight in the balanced case, we propose an algorithm to approximately solve the introduced transport problem. We obtain two novel characterizations of GW barycenters via multi-marginal GW plans. We show that for certain Gaussian inputs, the GW barycenter and associated multi-marginal problem admits a closed form solution. We stay in the context of GW transport problems and study the Riemannian structure of the induced GW space. Using tangent spaces, we propose novel approximation methods for the GW setting. Firstly, we define a linear GW distance and provide two alternative characterizations. We relax the linear GW distance so that it retains the valuable characteristics of the GW distance while reducing the computational complexity drastically when all distances between a large set of inputs are required. Secondly, we characterize tangential GW barycenters via multi-marginal plans which sparks a novel fixpoint iteration for the approximation of GW barycenters. We show that the iteration monotonously decreases the barycenter loss and converges subsequently to a fixpoint. In the final part of this thesis, we turn our attention to the estimation of dynamical systems via so-called transfer operators. The latter are linear operators which characterize the given dynamics between initial and final state in the form of density flows. Firstly, we discuss a completely unsupervised approach in the extreme setting when no correspondence information between initial and final state are known, but the system is expected to admit a governing isometric force such as rotations in Euclidean spaces. In this case, we show that GW transport plans are able to meaningfully approximate the true dynamics. Secondly, we propose a novel technique for transfer operator estimation when multiple batches of points in initial and final state are observed and the correspondence between the batches is known but the alignment within each batch is not. The technique is based on a maximum likelihood inference functional which is optimized over a hypothesis class coming from regularized OT kernels. We provide a relaxed version of the problem which can be tackled numerically via a generalized expectation-maximization-maximum-likelihood (EMML) algorithm. We show that the generalized EMML converges, increases the likelihood monotonously and adds no computational overhead to the classic EMML algorithm. A gamma-convergence result ensures that our model is able to recover the true dynamics of continuous systems by solving an approximate discrete problem. For both discussed methods, a spectral clustering method can be employed to extract macroscopic features of the estimated transfer operator. The thesis is accompanied by schematic figures and numerical experiments which illustrate the concepts and results.

Author dc:creator

• Beier, Florian

Advisor dc:contributor.advisor

• Steidl, Gabriele

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Identifier URI

https://doi.org/10.14279/depositonce-21336

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/22535