Graphical Optimal Transport: Theory, Algorithms, and Applications

本项目旨在发展数学理论和有效的算法来研究一类多边际最优运输(OT)方法。OT是一个流行的数学框架，在经济学、运筹学、生物学、信号处理、系统和控制以及数据科学等领域有许多应用。尽管如此，使用多个边缘的计算复杂性阻碍了它在实践中的使用，并且OT的大多数应用被限制在两个边缘。由此得到的框架将极大地扩展多边缘OT方法的应用。该项目还将包括一个重要的应用程序，通过总体测量来估计大量人口的群体行为。在群体/组中的个体彼此不可区分的意义上，测量是聚合的。这种测量可能是由于个人身份未公开的隐私问题而发生的。这项研究将有可能适用于研究这种疾病在大范围人群中的传播。最后，跨越多个学科的研究的跨学科性质将影响和交叉促进这些领域的科学和教育。本研究旨在建立具有图解成本的多边际OT问题的统一框架。与在应用中被广泛使用的双边缘OT不同，多边缘OT的使用因其臭名昭著的计算复杂性而受到阻碍，其计算复杂性通常随着边缘数量的增加而指数增长。尽管如此，多边际OT的复杂性可以通过利用其成本函数的结构来缓解。该项目将重点放在一种重要的成本结构上，这种结构将边缘部分编码为图表中的节点。许多多边际OT问题，如Wasserstein重心问题和不可压缩Euler流问题，都与这种图结构有关。这个项目将建立在两个看似不相干的主题上：最优运输和概率图形模型。研究者将通过两门学科的融合来建立图形化OT的总体框架，并系统地研究图形化OT的理论性质，特别是在状态变量连续的情况下。另一项重要的任务是通过利用OT和概率图形模型中的可用算法来开发有效的算法。最后，研究人员将把该框架应用于一个被称为聚合测量推理的代表性应用程序。在这类涉及大量个体的推理问题中，观测值以分布的形式聚集，该问题可以表示为一个熵正则多边际OT问题，其代价张量与隐马尔可夫模型相关联。该项目将为解决具有结构性成本的OT问题提供理论和算法工具，并极大地扩展多边际OT的应用领域。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.