Constrained Mass Optimal Transport

• URL: http://arxiv.org/abs/2206.13352v1
• Date: Sun, 5 Jun 2022 06:47:25 GMT
• Title: Constrained Mass Optimal Transport
• Authors: Said Kerrache and Yasushi Nakauchi
• Abstract summary: This paper introduces the problem of constrained optimal transport. A family of algorithms is introduced to solve a class of constrained saddle point problems. Convergence proofs and numerical results are presented.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal mass transport, also known as the earth mover's problem, is an optimization problem with important applications in various disciplines, including economics, probability theory, fluid dynamics, cosmology and geophysics to cite a few. Optimal transport has also found successful applications in image registration, content-based image retrieval, and more generally in pattern recognition and machine learning as a way to measure dissimilarity among data. This paper introduces the problem of constrained optimal transport. The time-dependent formulation, more precisely, the fluid dynamics approach is used as a starting point from which the constrained problem is defined by imposing a soft constraint on the density and momentum fields or restricting them to a subset of curves that satisfy some prescribed conditions. A family of algorithms is introduced to solve a class of constrained saddle point problems, which has convexly constrained optimal transport on closed convex subsets of the Euclidean space as a special case. Convergence proofs and numerical results are presented.

Related papers

• Neural Optimal Transport with Lagrangian Costs [29.091068250865504]
  We investigate the optimal transport problem between probability measures when the underlying cost function is understood to satisfy a Lagrangian cost. Our contributions are of computational interest, where we demonstrate the ability to efficiently compute geodesics and amortize spline-based paths. Unlike prior work, we also output the resulting Lagrangian optimal transport map without requiring an ODE solver.
  arXiv  Detail & Related papers  (2024-06-01T03:34:00Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sys is a framework that harnesses optimal transport theory for data repair under Conditional Independence (CI) constraints. We develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data.
  arXiv  Detail & Related papers  (2024-03-04T18:23:55Z)
• A Computational Framework for Solving Wasserstein Lagrangian Flows [48.87656245464521]
  In general, the optimal density path is unknown, and solving these variational problems can be computationally challenging. We propose a novel deep learning based framework approaching all of these problems from a unified perspective. We showcase the versatility of the proposed framework by outperforming previous approaches for the single-cell trajectory inference.
  arXiv  Detail & Related papers  (2023-10-16T17:59:54Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Online Learning to Transport via the Minimal Selection Principle [2.3857747529378917]
  We study the Online Learning Transport (OLT) problem where the decision variable is a convex, an-dimensional object. We derive a novel method called the minimal selection or exploration (SoMLT) algorithm to solve OLT problems using mean-field and discretization techniques.
  arXiv  Detail & Related papers  (2022-02-09T21:25:58Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution [8.465228064780748]
  We prove that computing the Wasserstein distance between a discrete probability measure supported on two points is already #P-hard. We introduce a distributionally robust dual optimal transport problem whose objective function is smoothed with the most adverse disturbance distributions. We show that smoothing the dual objective function is equivalent to regularizing the primal objective function.
  arXiv  Detail & Related papers  (2021-03-10T18:53:59Z)
• Relaxation of optimal transport problem via strictly convex functions [0.0]
  An optimal transport problem on finite spaces is a linear program. Recently, a relaxation of the optimal transport problem via strictly convex functions, especially via the Kullback--Leibler divergence, sheds new light on data sciences. This paper provides the mathematical foundations and an iterative process based on a gradient descent for the relaxed optimal transport problem via Bregman divergences.
  arXiv  Detail & Related papers  (2021-02-15T04:32:13Z)
• Fast Gravitational Approach for Rigid Point Set Registration with Ordinary Differential Equations [79.71184760864507]
  This article introduces a new physics-based method for rigid point set alignment called Fast Gravitational Approach (FGA) In FGA, the source and target point sets are interpreted as rigid particle swarms with masses interacting in a globally multiply-linked manner while moving in a simulated gravitational force field. We show that the new method class has characteristics not found in previous alignment methods.
  arXiv  Detail & Related papers  (2020-09-28T15:05:39Z)
• Scalable Differentiable Physics for Learning and Control [99.4302215142673]
  Differentiable physics is a powerful approach to learning and control problems that involve physical objects and environments. We develop a scalable framework for differentiable physics that can support a large number of objects and their interactions.
  arXiv  Detail & Related papers  (2020-07-04T19:07:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.