title: Advances in Gromov–Wasserstein optimal transport: linearization, multi-marginal generalization, barycenters and transfer operators
Creators: name: Beier, Florian
Publisher: name: Technische Universität Berlin
Year: 2024
Subjects: subject: 500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
subject: optimal transport
subject: Wasserstein
subject: Gromov-Wasserstein
subject: barycenter
subject: Frobenius-Perron operator

description: 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.
description: In den letzten Jahrzehnten hat sich das Forschungsfeld des optimalen Transports (OT) als wichtige Säule der modernen angewandten Mathematik etabliert. Der Fokus von OT sind Optimierungsprobleme, sogenannte Transportprobleme, dessen Lösungen sowohl zur Messung der Divergenz von Maßen sowie zur inneren Zuordnung zwischen den Maßen dienen. Die Art der Divergenz und Zuordnung hängt dabei von zugrundeliegenden Kosten ab, die es zu minimieren gilt. Die wachsende Beliebtheit von OT lässt sich insbesondere auf zahlreiche Daten, welche sich durch Maße modellieren lassen, die Möglichkeit aufgaben-entsprechend maßgeschneiderte Kosten einzusetzen, schnelle approximative Algorithmen zur Lösung von potenziell großskaligen Transportproblemen und dessen Generalisierbarkeit zurückführen. In dieser kumulativen Dissertation, entwickeln wir Theorie, Algorithmen und Anwendungen von generalisierten Transportenproblemen. Unser Hauptfokus liegt hierbei auf dem Gromov–Wasserstein-Transportproblem, kurz GW-Transportproblem, welches eine relaxierte Methode bietet, eine fast-isometrische Korrespondenz zwischen Maßen zu finden, und zu messen wie isometrisch die Maße sind. Nachdem wir verschiedene fundamentale Transportprobleme und die Notation eingeführt haben, präsentieren wir in thematisch eingeteilten Kapiteln unsere Hauptresultate. Zunächst richten wir unsere Aufmerksamkeit auf multi-marginale Transportprobleme welche essentiell in der Lage sind, simultane Zuordnungen zwischen einer beliebigen Anzahl an Maßen zu finden und diese zu vergleichen. Als erstes untersuchen wir das Kantorovich-Transportproblem in einem unbalancierten und multi-marginalen Kontext. Die induzierten multi-marginalen Transportpläne minimieren eine zugrundeliegende Kostenfunktion, welche auf dem Produktraum der Eingabemaße lebt. Aufgrund der unbalancierten Formulierung, können potenzielle Ausreißer oder Rauschen herausgefiltert werden. Wir erweitern einen beliebten approximativen Löser, nämlich den Sinkhorn-Algorithmus, auf diesen generalisierten Fall. Wir zeigen insbesondere, dass der Algorithmus unter schwachen Bedingungen konvergiert. Das neue Transportproblem kann verwendet werden, um unbalancierte OT-Baryzentren, also generalisierte Fréchet-Mittelwerte in Bezug auf die unbalancierte Kantorovich-Divergenz, zu charakterisieren. Für diesen Fall, kann der generalisierte Sinkhorn-Algorithmus effizient implementiert werden. Als zweites streben wir eine ähnliche Generalisierung im GW-Kontext an, was uns zum sogenannten (unbalancierten) multi-marginalen GW-Transportproblem führt. Wir stellen eine bikonvexe Relaxierung auf und zeigen, dass diese straff im balancierten Fall ist. Darüber hinaus führt die Relaxierung zu einem approximativen Algorithmus für das neue Transportproblem. Basierund auf multi-marginalen GW-Transportplänen, erhalten wir zwei neue Charakterisierungen von GW-Baryzentren. Schließlich zeigen wir, dass das multi-marginale Problem für Gauß Verteilungen eine Lösung in geschlossener Form hat. Als nächstes untersuchen wir die Riemannsche Struktur des GW-Raums, welcher duch die GW Distanz induziert wird. Basierend auf den Tangentialräumen des GW-Raums, stellen wir zwei approximative Methoden im GW-Kontext vor. Als erstes definieren wir die sogenannte lineare GW-Distanz und zeigen, dass diese zwei alternative Formulierungen besitzt. Wir betrachten eine Relaxierung, welche die charakteristischen Eigenschaften von der GW-Distanz erhält, den numerischen Aufwand jedoch deutlich reduziert, falls alle paarweisen Distanzen zwischen einer großen Menge von Eingaben benötigt werden. Als zweites zeigen wir, dass tangentiale GW-Baryzentren durch multi-marginale Transportpläne charakterisiert sind. Dieses Resultat liefert eine neue approximative Fixpunktiteration für die Bestimmung von GW-Baryzentren. Wir zeigen, dass die, durch die Iteration entstehende, Folge das Baryzentrum-Funktional monoton verringert. Weiterhin hat jede Teilfolge eine konvergente Teilfolge dessen Grenzwert ein Fixpunkt ist. Im letzten Teil dieser Dissertation betrachten wir die Schätzung von dynamischen Systemen durch sogenannte Transferoperatoren. Letztere sind lineare Operatoren, welche die Dynamik des Systems zwischen initialem und finalem Zustand durch Dichteflüsse beschreiben. Zuerst betrachten wir einen vollständig unüberwachten Ansatz im extremen Fall, dass keinerlei Informationen in Bezug auf die Korrespondenz zwischen initialem und finalem Zustand vorhanden sind. Unter der Annahme, dass das gegebene System hauptsächlich durch vorherrschende isometrische Kräfte bestimmt ist, beispielweise Rotationen im Euklidischen Fall, schlagen wir eine Approxmation durch GW Transportpläne vor. Als zweites betrachten wir einen alternativen teilüberwachten Fall. Hierbei sind initialer und finaler Zustand durch Punktserien charakterisiert, wobei die Zuordnung zwischen den Punktserien bekannt ist, während die Punktzuordnung innerhalb der Serien unbekannt ist. Basierend auf dieser Annahme, schlagen wir eine neue Methode zur Schätzung des Transferoperators vor. Diese basiert auf der Definition eines Maximum-Likelihood Inferenzfunktionals welches wir in der Praxis über eine Hypothesenmenge von Dichten optimieren, die aus entropischen OT Kernen konstruiert werden. Wir geben eine Relaxierung des Inferenzfunktionals vor, die wir mithilfe eines generalisierten Erwartungs-Maximierungs-Maximum-Likelihood-Algorithmus, kurz EMML-Algorithmus, lösen. Wir zeigen, dass dieser EMML Algorithmus konvergiert, das Likelihood-Funktional monoton erhöht und keinen rechnerischen Mehraufwand im Gegensatz zum klassichen EMML- Algorithmus verursacht. Wir liefern ein Gamma-Konvergenzresultat, welches uns erlaubt die echte Dynamik eines stetigen Systems durch diskrete Lösungen zu approximieren. Beide diskutierten approximativen Methoden lassen eine Spektralanalyse zu, mit dessen Hilfe makroskopische Eigenschaften des geschätzen Transferoperators zum Vorschein gebracht werden können. Die folgende Abhandlung wird durch schematische Diagramme und numerische Experimente begleitet, welche die diskutierten Konzepte und Resultate illustrieren.