A parallel framework for graphical optimal transport
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911292890021888 |
|---|---|
| author | Fan, Jiaojiao Haasler, Isabel Zhang, Qinsheng Karlsson, Johan Chen, Yongxin |
| author_facet | Fan, Jiaojiao Haasler, Isabel Zhang, Qinsheng Karlsson, Johan Chen, Yongxin |
| contents | We study multi-marginal optimal transport (MOT) problems where the underlying cost has a graphical structure. These graphical multi-marginal optimal transport problems have found applications in several domains including traffic flow control, barycenter and regression problems in the Wasserstein space, and Hidden Markov model inference problems. The MOT problem can be approached through two formulations: a single big MOT problem, or coupled minor OT problems. In this paper, we focus on the latter approach and demonstrate its efficiency gain from parallelization. For tree-structured MOT problems, we introduce a novel parallelizable algorithm that significantly reduces computational complexity. Additionally, we adapt this algorithm for general graphs, employing the modified junction trees to enable parallel updates. Our contributions, validated through numerical experiments, offer new avenues for MOT applications and establish benchmarks in computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A parallel framework for graphical optimal transport Fan, Jiaojiao Haasler, Isabel Zhang, Qinsheng Karlsson, Johan Chen, Yongxin Optimization and Control Computational Complexity We study multi-marginal optimal transport (MOT) problems where the underlying cost has a graphical structure. These graphical multi-marginal optimal transport problems have found applications in several domains including traffic flow control, barycenter and regression problems in the Wasserstein space, and Hidden Markov model inference problems. The MOT problem can be approached through two formulations: a single big MOT problem, or coupled minor OT problems. In this paper, we focus on the latter approach and demonstrate its efficiency gain from parallelization. For tree-structured MOT problems, we introduce a novel parallelizable algorithm that significantly reduces computational complexity. Additionally, we adapt this algorithm for general graphs, employing the modified junction trees to enable parallel updates. Our contributions, validated through numerical experiments, offer new avenues for MOT applications and establish benchmarks in computational efficiency. |
| title | A parallel framework for graphical optimal transport |
| topic | Optimization and Control Computational Complexity |
| url | https://arxiv.org/abs/2406.10849 |