Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.19246 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911560925970432 |
|---|---|
| author | Chen, Chunhui Chen, Jing Luo, Baojia Jin, Shi Wu, Hao |
| author_facet | Chen, Chunhui Chen, Jing Luo, Baojia Jin, Shi Wu, Hao |
| contents | Numerically solving multi-marginal optimal transport (MMOT) problems is computationally prohibitive, even for moderate-scale instances involving $l\ge4$ marginals with support sizes of $N\ge1000$. The cost in MMOT is represented as a tensor with $N^l$ elements. Even accessing each element once incurs a significant computational burden. In fact, many algorithms require direct computation of tensor-vector products, leading to a computational complexity of $O(N^l)$ or beyond. In this paper, inspired by our previous work [$Comm. \ Math. \ Sci.$, 20 (2022), pp. 2053 - 2057], we observe that the costly tensor-vector products in the Sinkhorn Algorithm can be computed with a recursive process by separating summations and dynamic programming. Based on this idea, we propose a fast tensor-vector product algorithm to solve the MMOT problem with $L^1$ cost, achieving a miraculous reduction in the computational cost of the entropy regularized solution to $O(N)$. Numerical experiment results confirm such high performance of this novel method which can be several orders of magnitude faster than the original Sinkhorn algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19246 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A numerical algorithm with linear complexity for Multi-marginal Optimal Transport with $L^1$ Cost Chen, Chunhui Chen, Jing Luo, Baojia Jin, Shi Wu, Hao Numerical Analysis Numerically solving multi-marginal optimal transport (MMOT) problems is computationally prohibitive, even for moderate-scale instances involving $l\ge4$ marginals with support sizes of $N\ge1000$. The cost in MMOT is represented as a tensor with $N^l$ elements. Even accessing each element once incurs a significant computational burden. In fact, many algorithms require direct computation of tensor-vector products, leading to a computational complexity of $O(N^l)$ or beyond. In this paper, inspired by our previous work [$Comm. \ Math. \ Sci.$, 20 (2022), pp. 2053 - 2057], we observe that the costly tensor-vector products in the Sinkhorn Algorithm can be computed with a recursive process by separating summations and dynamic programming. Based on this idea, we propose a fast tensor-vector product algorithm to solve the MMOT problem with $L^1$ cost, achieving a miraculous reduction in the computational cost of the entropy regularized solution to $O(N)$. Numerical experiment results confirm such high performance of this novel method which can be several orders of magnitude faster than the original Sinkhorn algorithm. |
| title | A numerical algorithm with linear complexity for Multi-marginal Optimal Transport with $L^1$ Cost |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2405.19246 |