Approximating Optimal Transport via Low-rank and Sparse Factorization

• URL: http://arxiv.org/abs/2111.06546v1
• Date: Fri, 12 Nov 2021 03:10:45 GMT
• Title: Approximating Optimal Transport via Low-rank and Sparse Factorization
• Authors: Weijie Liu, Chao Zhang, Nenggan Zheng, Hui Qian
• Abstract summary: Optimal transport (OT) naturally arises in a wide range of machine learning applications but may often become the computational bottleneck. A novel approximation for OT is proposed, in which the transport plan can be decomposed into the sum of a low-rank matrix and a sparse one.
• Score: 19.808887459724893
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Optimal transport (OT) naturally arises in a wide range of machine learning applications but may often become the computational bottleneck. Recently, one line of works propose to solve OT approximately by searching the \emph{transport plan} in a low-rank subspace. However, the optimal transport plan is often not low-rank, which tends to yield large approximation errors. For example, when Monge's \emph{transport map} exists, the transport plan is full rank. This paper concerns the computation of the OT distance with adequate accuracy and efficiency. A novel approximation for OT is proposed, in which the transport plan can be decomposed into the sum of a low-rank matrix and a sparse one. We theoretically analyze the approximation error. An augmented Lagrangian method is then designed to efficiently calculate the transport plan.

Related papers

• Overcoming Fake Solutions in Semi-Dual Neural Optimal Transport: A Smoothing Approach for Learning the Optimal Transport Plan [5.374547520354591]
  Semi-dual Neural OT, a widely used approach for learning OT Maps with neural networks, often generates fake solutions that fail to transfer one distribution to another accurately. We propose a novel method, OTP, which learns both the OT Map and the Optimal Transport Plan, representing the optimal coupling between two distributions. Our experiments show that the OTP model recovers the optimal transport map where existing methods fail and outperforms current OT-based models in image-to-image translation tasks.
  arXiv  Detail & Related papers  (2025-02-07T00:37:12Z)
• A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers [65.28989155951132]
  In this paper, we establish upper bounds on the generalization error of an approximate OT map recovered by the minimax quadratic OT solver. While our analysis focuses on the quadratic OT, we believe that similar bounds could be derived for more general OT formulations.
  arXiv  Detail & Related papers  (2025-02-03T12:37:20Z)
• Convex Physics Informed Neural Networks for the Monge-Ampère Optimal Transport Problem [49.1574468325115]
  Optimal transportation of raw material from suppliers to customers is an issue arising in logistics. A physics informed neuralnetwork method is advocated here for the solution of the corresponding generalized Monge-Ampere equation. A particular focus is set on the enforcement of transport boundary conditions in the loss function.
  arXiv  Detail & Related papers  (2025-01-17T12:51:25Z)
• Expected Sliced Transport Plans [9.33181953215826]
  We propose a "lifting" operation to extend one-dimensional optimal transport plans back to the original space of the measures. We prove that using the EST plan to weight the sum of the individual Euclidean costs for moving from one point to another results in a valid metric between the input discrete probability measures.
  arXiv  Detail & Related papers  (2024-10-16T02:44:36Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOT is an information-theoretic extension of optimal transport. It maximizes the mutual information between domains while minimizing geometric distances. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples.
  arXiv  Detail & Related papers  (2022-10-06T18:55:41Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Neural Optimal Transport [82.2689844201373]
  We present a novel neural-networks-based algorithm to compute optimal transport maps and plans for strong and weak transport costs. We prove that neural networks are universal approximators of transport plans between probability distributions.
  arXiv  Detail & Related papers  (2022-01-28T16:24:13Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Order Constraints in Optimal Transport [6.677646909984405]
  We introduce novel order constraints into the optimal transport formulation to allow for the incorporation of structure. We derive computationally efficient lower bounds that allow for an explainable approach to adding structure to the optimal transport plan.
  arXiv  Detail & Related papers  (2021-10-14T11:26:23Z)
• Linearized Optimal Transport for Collider Events [0.0]
  We introduce an efficient framework for computing the distance between collider events using the tools of Linearized Optimal Transport (LOT) It also furnishes a Euclidean embedding amenable to simple machine learning algorithms and visualization techniques.
  arXiv  Detail & Related papers  (2020-08-19T18:00:09Z)

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.