2020/04/15 by Isabel Haasler, Axel Ringh, Haasler, Isabel +5
Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2004.06909
openalex publication_date 2020/04/15 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
The optimal transport problem has recently developed into a powerful\nframework for various applications in estimation and control. Many of the\nrecent advances in the theory and application of optimal transport are based on\nregularizing the problem with an entropy term, which connects it to the\nSchr "odinger bridge problem and thus to stochastic optimal control. Moreover,\nthe entropy regularization makes the otherwise computationally demanding\noptimal transport problem feasible even for large scale settings. This has lead\nto an accelerated development of optimal transport based methods in a broad\nrange of fields. Many of these applications have a underlying graph structure,\nfor instance information fusion and tracking problems can be described by\ntrees. In this work we consider multi-marginal optimal transport problems with\na cost function that decouples according to a tree structure. The entropy\nregularized multi-marginal optimal transport problem can be viewed as a\ngeneralization of the Schr "odinger bridge problem with the same\ntree-structure, and by utilizing these connections we extend the computational\nmethods for the classical optimal transport problem in order to solve\nstructured multi-marginal optimal transport problems in an efficient manner. In\nparticular, the algorithm requires only matrix-vector multiplications of\nrelatively small dimensions. We show that the multi-marginal regularization\nintroduces less diffusion, compared to the commonly used pairwise\nregularization, and is therefore more suitable for many applications. Numerical\nexamples illustrate this, and we finally apply the proposed framework for\ntracking of an ensemble of indistinguishable agents.\n