Gromov-Wasserstein Distances and their Lower Bounds
von Christoph Alexander Weitkamp
Datum der mündl. Prüfung:2022-07-07
Betreuer:Prof. Dr. Axel Munk
Gutachter:Prof. Dr. Axel Munk
Gutachter:Dr. Katharina Proksch
EnglischIn various applications in biochemistry, computer vision and machine learning, it is of great interest to compare general objects in a pose invariant manner. Recently, the following approach has received increased attention: Model the objects considered as metric measure spaces and compare them with the Gromov-Wasserstein distance. While this distance has many theoretically appealing properties and is a natural distance concept in numerous frameworks, it is NP-hard to compute. In consequence, several alternatives to the precise determination of this distance have been proposed. On the one hand, it is possible to approximate local optima of the minimization problem corresponding to the calculation of the Gromov-Wasserstein distance by conditional gradient descent. On the other hand, one can work with efficiently computable surrogates and lower bounds for the previously mentioned distance. This PhD-thesis consists of three research articles that pursue the second approach. More precisely, the first article investigates the statistical potential of a known meaningful lower bound based on distributions of pairwise distances. Its findings are employed for the comparison of 3d-protein structures. The second article proposes a new Gromov-Wasserstein based surrogate specifically tailored for comparing ultrametric measure spaces and explores its theoretical properties. Finally, the third article is concerned with chromatin loop analysis based on average nearest neighbor distance distributions, which are closely related to and in particular stable under the Gromov-Wasserstein distance.
Keywords: Gromov-Wasserstein; Distribution of distances; Ultrametric spaces; Distance-to-Measure signature