Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
From MaRDI portal
Publication:6173517
Abstract: By adding entropic regularization, multi-marginal optimal transport problems can be transformed into tensor scaling problems, which can be solved numerically using the multi-marginal Sinkhorn algorithm. The main computational bottleneck of this algorithm is the repeated evaluation of marginals. Recently, it has been suggested that this evaluation can be accelerated when the application features an underlying graphical model. In this work, we accelerate the computation further by combining the tensor network dual of the graphical model with additional low-rank approximations. We provide an example for the color transfer between several images, in which these additional low-rank approximations save more than 96% of the computation time.
Recommendations
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Fast iterative solution of the optimal transport problem on graphs
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
Cites work
- A linear optimal transportation framework for quantifying and visualizing variations in sets of images
- A literature survey of low-rank tensor approximation techniques
- A numerical method to solve multi-marginal optimal transport problems with Coulomb cost
- A practical introduction to tensor networks: Matrix product states and projected entangled pair states
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm
- Barycenters in the Wasserstein space
- Computational optimal transport. With applications to data sciences
- D//\(1AD_ 2 \)theorems for multidimensional matrices
- Duality of graphical models and tensor networks
- Elements of Information Theory
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- From the Schrödinger problem to the Monge-Kantorovich problem
- Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
- Inference in belief networks: A procedural guide
- Iterative Bregman projections for regularized transportation problems
- Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- Multi-marginal optimal transport: theory and applications
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
- Numerical methods for matching for teams and Wasserstein barycenters
- On the linear convergence of the multimarginal Sinkhorn algorithm
- On the scaling of multidimensional matrices
- Optimal Transport
- Optimal transportation theory with repulsive costs
- Optimal transportation, modelling and numerical simulation
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Tensor Decompositions and Applications
- Tensor network contractions. Methods and applications to quantum many-body systems
- Tensor-train decomposition
- The Interplay Between Entropy and Variational Distance
- Unbalanced multi-marginal optimal transport
Cited in
(8)- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- A Low-Rank Tensor Method for PDE-Constrained Optimization with Isogeometric Analysis
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Scalable computation of dynamic flow problems via multimarginal graph-structured optimal transport
- Efficient and exact multimarginal optimal transport with pairwise costs
- Convergence proof for the GenCol algorithm in the case of two-marginal optimal transport
- Approximating maps into manifolds with lower curvature bounds
- Synchronized optimal transport for joint modeling of dynamics across multiple spaces
This page was built for publication: Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6173517)
