Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
From MaRDI portal
Publication:5000631
Abstract: The optimal transport problem has recently developed into a powerful framework for various applications in estimation and control. Many of the recent advances in the theory and application of optimal transport are based on regularizing the problem with an entropy term, which connects it to the Schr"odinger bridge problem and thus to stochastic optimal control. Moreover, the entropy regularization makes the otherwise computationally demanding optimal transport problem feasible even for large scale settings. This has lead to an accelerated development of optimal transport based methods in a broad range of fields. Many of these applications have a underlying graph structure, for instance information fusion and tracking problems can be described by trees. In this work we consider multi-marginal optimal transport problems with a cost function that decouples according to a tree structure. The entropy regularized multi-marginal optimal transport problem can be viewed as a generalization of the Schr"odinger bridge problem with the same tree-structure, and by utilizing these connections we extend the computational methods for the classical optimal transport problem in order to solve structured multi-marginal optimal transport problems in an efficient manner. In particular, the algorithm requires only matrix-vector multiplications of relatively small dimensions. We show that the multi-marginal regularization introduces less diffusion, compared to the commonly used pairwise regularization, and is therefore more suitable for many applications. Numerical examples illustrate this, and we finally apply the proposed framework for tracking of an ensemble of indistinguishable agents.
Recommendations
- An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm
- THE MULTI-MARGINAL OPTIMAL PARTIAL TRANSPORT PROBLEM
- Multi-marginal optimal transport: theory and applications
- Optimal transport with branching distance costs and the obstacle problem
- On deterministic solutions for multi-marginal optimal transport with Coulomb cost
- Solutions to multi-marginal optimal transport problems concentrated on several graphs
- Multimarginal Optimal Transport Maps for One–dimensional Repulsive Costs
- On the local structure of optimal measures in the multi-marginal optimal transportation problem
- On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
- Multi-marginal optimal transport on Riemannian manifolds
Cites work
- scientific article; zbMATH DE number 410740 (Why is no real title available?)
- scientific article; zbMATH DE number 4080537 (Why is no real title available?)
- scientific article; zbMATH DE number 789259 (Why is no real title available?)
- A survey of the Schrödinger problem and some of its connections with optimal transport
- Barycenters in the Wasserstein space
- Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
- Discrete-time classical and quantum Markovian evolutions: maximum entropy problems on path space
- Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
- Dykstras algorithm with bregman projections: A convergence proof
- Elements of Information Theory
- Entropic and displacement interpolation: a computational approach using the Hilbert metric
- Entropy, large deviations, and statistical mechanics.
- Extended mean field control problems: stochastic maximum principle and transport perspective
- Fokker-Planck equations for a free energy functional or Markov process on a graph
- From the Schrödinger problem to the Monge-Kantorovich problem
- Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
- Graph theory
- Iterative Bregman projections for regularized transportation problems
- Martingale optimal transport with stopping
- Measure-Valued Spline Curves: An Optimal Transport Viewpoint
- Monge's problem with a quadratic cost by the zero-noise limit of \(h\)-path processes
- Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- Multi-marginal Schrödinger bridges
- Multi-marginal optimal transport: theory and applications
- On the \(n\)-coupling problem
- On the convergence of the coordinate descent method for convex differentiable minimization
- On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
- On the scaling of multidimensional matrices
- Optimal Steering of a Linear Stochastic System to a Final Probability Distribution, Part I
- Optimal Transport
- Optimal Transportation Problem by Stochastic Optimal Control
- Optimal maps for the multidimensional Monge-Kantorovich problem
- Optimal solutions of multivariate coupling problems
- Optimal transport with controlled dynamics and free end times
- Positive contraction mappings for classical and quantum Schrödinger systems
- Reciprocal classes of random walks on graphs
- Reciprocal processes
- Robust Transport Over Networks
- Sample-based population observers
- Schrödinger processes and large deviations
- State distributions and minimum relative entropy noise sequences in uncertain stochastic systems: the discrete-time case
- Structure theory for ensemble controllability, observability, and duality
- The Markov processes of Schr�dinger
- Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems
Cited in
(15)- Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
- Estimating pollution spread in water networks as a Schrödinger bridge problem with partial information
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Efficient and exact multimarginal optimal transport with pairwise costs
- Graph-structured tensor optimization for nonlinear density control and mean field games
- Monge-Kantorovich optimal transport through constrictions and flow-rate constraints
- Simple approximative algorithms for free-support Wasserstein barycenters
- Entropic model predictive optimal transport over dynamical systems
- Wasserstein Barycenters Are NP-Hard to Compute
- Optimal transport over nonlinear systems via infinitesimal generators on graphs
- Unbalanced multi-marginal optimal transport
- On the linear convergence of the multimarginal Sinkhorn algorithm
- A family of pairwise multi-marginal optimal transports that define a generalized metric
- An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm
- Constrained Hellinger-Kantorovich barycenters: least-cost soft and conic multimarginal formulations
This page was built for publication: Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000631)
