Collaborative proposal: Geometric methods for optimal matching and feature identification in data se

This proposal describes a series of interconnected projects organized around the theme of optimization in geometric data analysis.,Some data has inherent geometry; for other data, geometric data analysis uses combinatorial methods to produce a geometric object th,at can then be studied by geometric means. This project explores how geometric methods can be applied to seek optimal matchings bet,ween data collected from different sources or different measurement modalities for the same data. The geometric features of the geo,metric object constructed from abstract data often have concrete meaning in terms of the original data. The project describes techn,iques to identify features in data by searching for embeddings of optimal representatives of geometric structures. Optimal matching, problemsA core problem in data analysis is the following: Given two finite metric spaces (X,d_X) and (Y,d_Y), find a matching for t,he points of X and Y that minimizes some loss function reflecting metric distortion (e.g., the Gromov-Wasserstein distance). The ov,erhead of direct methods makes application to moderately-sized data sets infeasible, even under aggressive relaxations. In prior wo,rk, the PIs (and collaborators) introduced a new method for approximating such matchings on very large data sets. The proposed work, builds on this foundation in a number of different directions: subset matchings, dimensionality reduction via matching, and metric,inference via markers. Each of these thrusts has broad applicability to problems arising in real data.Optimal loop identificationDa,ta sets from time series or with a time component often display periodic or quasi-periodic behavior. Minimal loops that arise in th,ese data sets are the basic building blocks of qualitative descriptions of the dynamical behavior. A key problem is to determine th,e size and location of these loops from finite samples. In prior work, PIs Blumberg and Mandell introduced theoretical foundations,for identifying loops (and more complicated geometric motifs) in data sets using ideas from quantitative algebraic topology. That w,ork is based on extending the classical idea of the fundamental group pi_1(X) of a space X, which provides a way of studying loops i,n X: it develops a quantitative version of pi_1 that records the length of the loops. The proposed research will develop efficient,algorithms for applying these ideas in the context of optimal loop identification. The proposed research will develop robust algori,thms for optimal matching problems and optimal loop identification with wide applicability to signals from many sources. If success,ful, this research will introduce a new toolkit for solving optimization problems in geometric data analysis and using this to descr,ibe qualitative features of data.