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.

När objekt inte är direkt jämförbara med varandra behövs sätt att hitta korrespondenser mellan detaljer i objekten givet att man har ett sätt att värdera interna relationer inom objekten. Patienters resor genom en behandling och organismers olika morfologi är exempel på sådana objekt. Om man har gjort det möjligt att jämföra objekt med varandra är det sedan möjligt att förstå  hur dessa variationer ter sig. Klustring, dvs gruppering av information för att förenkla en stor datamängd till en mindre mängd grupper och hur dessa förhåller sig till varandra är ett sätt att skapa sig en uppfattning om hela fördelningen.

Denna avhandling behandlar kognitiva modeller för att avgöra diskreptanser mellan metriska måttrum, optimala korrespondenser mellan detaljer i objekt samt gruppering och klustring av data. Dessa tillhör en klass av optimeringsproblem som kallas icke-konvexa tilldelningsproblem. Syftet med avhandlingen är att  möjliggöra att lösa dessa typer av problem exakt och skapa algoritmer som gör det möjligt att lösa dessa problem effektivt. Detta får konsekvenser i ökad korrekthet när metoderna används i naturvetenskaperna för att analysera tillstånd, t.ex. vid läkemedelsutveckling. 

Den första artikeln behandlar jämförelser mellan punktmoln. Punktmoln som är en diskretisering av metriska måttrum kan anses isometriska, vilket för vektorrum betyder att det finns en translation och rotation så att de blir identiska. Om detta inte kan ske vill man skapa sig en diskreptans som beskriver hur skilt från isometriska två punktmoln är från varandra. På detta sätt kan data som är deformerat eller saknar information ändå bli jämfört med andra datamoln. Med utgångspunkt i Gromov-Hausdorff distansen och Gromov-Wasserstein distansen presenteras en metod att beräkna denna diskreptans för mångdimensionella moln som effektivt konvergerar till den exakta lösningen och blir praktiskt användbar för t.ex. mikroskopidata. Metoden grundar sig på en halv-plansmetod som approximerar rummet av godkända lösningar effektivt i närheten av de lokalt optimala lösningarna, och bevisar konvergens för konkava kvadratiska problem.

I den andra artikeln återkommer vi till Gromov-Wasserstein problemet, formulerar en lågdimensionell variant för diskreta metriska måttrum och utvecklar konceptet för problem där all information ej är tillgänglig samt för multi-marginala problem. Med detta kan man lösa tyngdpunkter, dvs bästa mellanting mellan olika metriska mått-rum. Detta har applikationer för 3d-rekonstuktion av t.ex. proteiner i elektronmikroskop och en möjlighet att med väldigt lite struktur kunna avgöra morfologiska skillnader och isomerismer, t.ex. kiraliteter. Metoden används också för att lösa det sk dimensionsreduceringsproblement till global optimalitet för några enkla problem. Halvplansmetoden utvidgas till att hantera en mix av konvexa och konkava objektfunktioner.

I den tredje artikeln behandlas problemet kring gruppering av data, där en metod presenteras för hitta den globalt optimala minsta kvadratsumman av avstånd mellan en mängd datapunkter i ett lågdimensionellt rum till en begränsad uppsättning centroider, som skalar väl med antalet datapunkter. Metoden är relaterad till det även på svenska kallade k-means problemet. Metoden utvecklar den sk halv-plansmetoden för generella konkava problem, och inkluderar tekniker för att minska antalet globala lösningar om det existerar symmetrier.

Den fjärde artikeln behandlar gruppering av data där datat är jämförd med någon vald distans. När datat innehåller stora mängder brus och grupperingarna har komplicerade geometrier behöver dessa varsamt separeras från varandra. Artikeln introducerar en metod som förstärker den sk. diffusionsdistansen mellan datapunkterna och bevisar att detta kan ske unikt för små förstärkningar.