Graphical Optimal Transport: Theory, Algorithms, and Applications

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project aims to develop mathematical theories and efficient algorithms to study a class of multi-marginal optimal transport (OT) methods. OT is a popular mathematical framework that has found many applications in several areas such as economics, operations research, biology, signal processing, systems and control, and data science. Still, the computational complexity of using multiple marginals hinders its use in practice, and most applications of OT are limited to two marginals. The resulting framework will greatly expand the applications of OT methods with multiple marginals. The project will also include an important application, estimating the group behavior of a large population with aggregate measurements. The measurements are aggregated in the sense that the individuals in the population/group are indistinguishable from each other. Such measurement may occur due to privacy issues where the identities of the individuals are unrevealed. This study will be potentially applicable to studying the disease spreading in a large population. Finally, the interdisciplinary nature of the research bridging multiple subjects will impact and cross-fertilize science and education in these areas. This research aims to establish a unified framework for multi-marginal OT problems with graphical costs. Unlike bi-marginal OT, which has been widely used in applications, the use of multi-marginal OT has been hindered by its notorious computational complexity that typically grows exponentially as the number of marginals increases. Still, the complexity of multi-marginal OT can be alleviated by exploiting the structures of its cost function. The project will focus on an important type of cost structure that encodes the marginals as nodes in a graph. Many multi-marginal OT problems such as the Wasserstein barycenter and the incompressible Euler flow problems are associated with such graphical structures. This project will build on two seemly irrelevant subjects: optimal transport and probabilistic graphical models. The investigator will establish the overall framework of graphical OT by merging the two subjects, and systematically investigate the theoretical properties of graphical OT, particularly in the setting with continuous state variables. Another important task is to develop efficient algorithms by leveraging available algorithms in both OT and probabilistic graphical models. Finally, the investigator will apply the framework to a representative application known as inference with aggregate measurements. In this type of inference problem involving a large population of individuals, the observations are aggregated in the form of distributions, and the problem can be formulated as an entropy regularized multi-marginal OT problem whose cost tensor is associated with a hidden Markov model. The project will provide theoretical and algorithmic tools for addressing OT problems with structured costs, and greatly expand the application domains of multi-marginal OT. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.