权益分类	功能权益	普通用户	{{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 的复杂性可以通过利用其成本函数的结构来减轻。该项目将重点关注一种重要的成本结构类型，它将边际编码为图中的节点。许多多边际 OT 问题（例如 Wasserstein 重心和不可压缩欧拉流问题）都与此类图形结构相关。该项目将建立在两个看似不相关的主题之上：最优传输和概率图形模型。研究者将通过合并两个主题来建立图形 OT 的整体框架，并系统地研究图形 OT 的理论特性，特别是在连续状态变量的设置中。另一项重要任务是利用 OT 和概率图模型中的可用算法来开发高效的算法。最后，研究人员将该框架应用于称为聚合测量推理的代表性应用程序。在涉及大量个体的此类推理问题中，观测值以分布的形式聚合，并且该问题可以表示为熵正则化多边际 OT 问题，其成本张量与隐马尔可夫模型相关。该项目将为解决结构化成本的OT问题提供理论和算法工具，并极大地扩展多边际OT的应用领域。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，认为值得支持。