Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
From MaRDI portal
Publication:5000631
DOI10.1137/20M1320195zbMATH Open1467.93329arXiv2004.06909OpenAlexW3182348197MaRDI QIDQ5000631FDOQ5000631
Authors: Isabel Haasler, Axel Ringh, Yongxin Chen, Johan Karlsson 
Publication date: 15 July 2021
Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2004.06909
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
hidden Markov chaingraph signal processingmultimarginal optimal transportSchrödinger bridgeensemble estimation
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Estimation and detection in stochastic control theory (93E10) Optimal stochastic control (93E20)
Cites Work
- Elements of Information Theory
- Graph theory
- Barycenters in the Wasserstein space
- Optimal Transport
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems
- Title not available (Why is that?)
- Optimal maps for the multidimensional Monge-Kantorovich problem
- Monge's problem with a quadratic cost by the zero-noise limit of \(h\)-path processes
- Fokker-Planck equations for a free energy functional or Markov process on a graph
- Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
- Reciprocal processes
- From the Schrödinger problem to the Monge-Kantorovich problem
- Iterative Bregman projections for regularized transportation problems
- On the \(n\)-coupling problem
- Entropy, large deviations, and statistical mechanics.
- On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
- Optimal Steering of a Linear Stochastic System to a Final Probability Distribution, Part I
- Entropic and displacement interpolation: a computational approach using the Hilbert metric
- Optimal Transportation Problem by Stochastic Optimal Control
- A survey of the Schrödinger problem and some of its connections with optimal transport
- Title not available (Why is that?)
- The Markov processes of Schr�dinger
- Positive contraction mappings for classical and quantum Schrödinger systems
- Discrete-time classical and quantum Markovian evolutions: maximum entropy problems on path space
- Title not available (Why is that?)
- Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
- On the scaling of multidimensional matrices
- Schrödinger processes and large deviations
- On the convergence of the coordinate descent method for convex differentiable minimization
- Reciprocal classes of random walks on graphs
- Multi-marginal optimal transport: theory and applications
- Optimal solutions of multivariate coupling problems
- Robust Transport Over Networks
- Dykstras algorithm with bregman projections: A convergence proof
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
- Measure-Valued Spline Curves: An Optimal Transport Viewpoint
- State distributions and minimum relative entropy noise sequences in uncertain stochastic systems: the discrete-time case
- Sample-based population observers
- Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
- Extended mean field control problems: stochastic maximum principle and transport perspective
- Optimal transport with controlled dynamics and free end times
- Martingale optimal transport with stopping
- Structure theory for ensemble controllability, observability, and duality
- Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- Multi-marginal Schrödinger bridges
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
Uses Software
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)
