权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Graphical Optimal Transport: Theory, Algorithms, and Applications

图形优化传输：理论、算法和应用

基本信息

批准号：
2206576
负责人：
Yongxin Chen
金额：
$ 24万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-09-15 至 2025-08-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2206576&HistoricalAwards=false
关键词：
Graphical Optimal Transport Theory Algorithms

项目摘要

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.

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