Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized incompressible flows, multi-marginal transport and Sinkhorn algorithm
305
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Starting from Breniers relaxed formulation of the incompressible Euler equation in terms of geodesics in the group of measure-preserving diffeomorphisms, we propose a numerical method based on Sinkhorns algorithm for the entropic regularization of optimal transport. We also make a detailed comparison of this entropic regularization with the so-called Bredinger entropic interpolation problem. Numerical results in dimension one and two illustrate the feasibility of the method.
rate research
Read More
We provide a computational complexity analysis for the Sinkhorn algorithm that solves the entropic regularized Unbalanced Optimal Transport (UOT) problem between two measures of possibly different masses with at most $n$ components. We show that the complexity of the Sinkhorn algorithm for finding an $varepsilon$-approximate solution to the UOT problem is of order $widetilde{mathcal{O}}(n^2/ varepsilon)$, which is near-linear time. To the best of our knowledge, this complexity is better than the complexity of the Sinkhorn algorithm for solving the Optimal Transport (OT) problem, which is of order $widetilde{mathcal{O}}(n^2/varepsilon^2)$. Our proof technique is based on the geometric convergence of the Sinkhorn updates to the optimal dual solution of the entropic regularized UOT problem and some properties of the primal solution. It is also different from the proof for the complexity of the Sinkhorn algorithm for approximating the OT problem since the UOT solution does not have to meet the marginal constraints.
We study multi-marginal optimal transport, a generalization of optimal transport that allows us to define discrepancies between multiple measures. It provides a framework to solve multi-task learning problems and to perform barycentric averaging. However, multi-marginal distances between multiple measures are typically challenging to compute because they require estimating a transport plan with $N^P$ variables. In this paper, we address this issue in the following way: 1) we efficiently solve the one-dimensional multi-marginal Monge-Wasserstein problem for a classical cost function in closed form, and 2) we propose a higher-dimensional multi-marginal discrepancy via slicing and study its generalized metric properties. We show that computing the sliced multi-marginal discrepancy is massively scalable for a large number of probability measures with support as large as $10^7$ samples. Our approach can be applied to solving problems such as barycentric averaging, multi-task density estimation and multi-task reinforcement learning.
It is known from clever mathematical examples cite{Ca10} that the Monge ansatz may fail in continuous two-marginal optimal transport (alias optimal coupling alias optimal assignment) problems. Here we show that this effect already occurs for finite assignment problems with $N=3$ marginals, $ell=3$ sites, and symmetric pairwise costs, with the values for $N$ and $ell$ both being optimal. Our counterexample is a transparent consequence of the convex geometry of the set of symmetric Kantorovich plans for $N=ell=3$, which -- as we show -- possess 22 extreme points, only 7 of which are Monge. These extreme points have a simple physical meaning as irreducible molecular packings, and the example corresponds to finding the minimum energy packing for Frenkel-Kontorova interactions. Our finite example naturally gives rise, by superposition, to a continuous one, where failure of the Monge ansatz manifests itself as nonattainment and formation of microstructure.
We discover a new class of topological solitons. These solitons can exist in a space of infinite volume like, e.g., $mathbb{R}^n$, but they cannot be placed in any finite volume, because the resulting formal solutions have infinite energy. These objects are, therefore, interpreted as totally incompressible solitons. As a first, particular example we consider (1+1) dimensional kinks in theories with a nonstandard kinetic term or, equivalently, in models with the so-called runaway (or vacummless) potentials. But incompressible solitons exist also in higher dimensions. As specific examples in (3+1) dimensions we study Skyrmions in the dielectric extensions both of the minimal and the BPS Skyrme models. In the the latter case, the skyrmionic matter describes a completely incompressible topological perfect fluid.
In this paper, we present a numerical method, based on iterative Bregman projections, to solve the optimal transport problem with Coulomb cost. This is related to the strong interaction limit of Density Functional Theory. The first idea is to introduce an entropic regularization of the Kantorovich formulation of the Optimal Transport problem. The regularized problem then corresponds to the projection of a vector on the intersection of the constraints with respect to the Kullback-Leibler distance. Iterative Bregman projections on each marginal constraint are explicit which enables us to approximate the optimal transport plan. We validate the numerical method against analytical test cases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
