Methods and algorithms for optimal correspondences and assignments in data exploration

QC 2025-02-07

Abstract

When objects are not directly comparable with each other, methods are needed to identify correspondences between details of the objects given that there is a way to evaluate internal relationships. Patients' journeys through treatment and the varying morphology of organisms are examples of such objects. Once it is possible to compare objects with each other, it is possible to understand how these variations manifest. Clustering, i.e., grouping information to simplify a large dataset into a smaller number of groups and understanding how these groups relate to one another, is one way to gain an understanding of the overall distribution.

This thesis addresses cognitive models for determining discrepancies between metric measure spaces, optimal correspondences between object details, and data clustering. These models belong to a class of optimization problems called non-convex assignment problems. The aim of the thesis is to provide ways to solve these types of problems to global optimality and to develop algorithms that enable efficient computations. This has consequences of increased accuracy when they are used in natural sciences to measure states, for example in pharmaceutical development.

The first article focuses on comparisons between point clouds. Point clouds, which may be a discretization of metric measure spaces, can be considered isometric if there exists a distance preserving function such as translations or rotations in vector spaces that make them identical. If this is not possible, a notion of distance is sought to describe how different two point clouds are from being isometric. This allows data that is deformed or incomplete to still be compared with other datasets. Based on the Gromov-Hausdorff and Gromov-Wasserstein distances, the article presents a method to calculate such a discrepancy for multidimensional clouds that converges efficiently to the exact solution and becomes practically applicable, for example, for microscopy data. The method is based on a cutting-plane method that approximates the space of admissible solutions efficiently near the local optimal solutions and proves convergence for concave quadratic problems.

In the second article, we revisit the Gromov-Wasserstein problem, formulating a low-dimensional variant for discrete metric measure spaces and developing the concept for problems when the measures are only partly observable and problems that are multi-marginal. With this, it is possible to solve barycenters, i.e., the best compromise between different metric measure spaces. This has applications in 3D reconstruction, for example, of proteins in electron microscopy, and provides a way to determine morphological differences and isomerisms with very little structure, such as chiralities. The method is also used to solve the so-called dimensionality reduction problem to global optimality for some simple cases. The cutting plane method is extended to handle a mix of convex and concave objective functions.

In the third article, the problem of data clustering is considered, where a method is presented for finding the globally optimal minimum sum of squared distances between a set of data points in a low-dimensional space and a limited set of centroids, often called the k-means problem, which scales well with the number of data points. The method extends the so-called cutting-plane method to general concave problems, and includes techniques such as symmetry breaking.

The fourth article deals with data clustering, where the data is compared using a fixed but arbitrary distance. When the data contains large amounts of noise and the clusters have complex geometries, careful separation is required. The article introduces a method that enhances the so-called diffusion distance between data points and proves that this can be done uniquely for small enhancements.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-359682