Sliced Optimal Partial Transport

• URL: http://arxiv.org/abs/2212.08049v9
• Date: Mon, 7 Aug 2023 17:09:10 GMT
• Title: Sliced Optimal Partial Transport
• Authors: Yikun Bai and Berhnard Schmitzer and Mathew Thorpe and Soheil Kolouri
• Abstract summary: We propose an efficient algorithm for calculating the Optimal Partial Transport problem between two non-negative measures in one dimension. We demonstrate the computational and accuracy benefits of the sliced OPT-based method in various numerical experiments.
• Score: 13.595857406165292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT) has become exceedingly popular in machine learning, data science, and computer vision. The core assumption in the OT problem is the equal total amount of mass in source and target measures, which limits its application. Optimal Partial Transport (OPT) is a recently proposed solution to this limitation. Similar to the OT problem, the computation of OPT relies on solving a linear programming problem (often in high dimensions), which can become computationally prohibitive. In this paper, we propose an efficient algorithm for calculating the OPT problem between two non-negative measures in one dimension. Next, following the idea of sliced OT distances, we utilize slicing to define the sliced OPT distance. Finally, we demonstrate the computational and accuracy benefits of the sliced OPT-based method in various numerical experiments. In particular, we show an application of our proposed Sliced-OPT in noisy point cloud registration.

Related papers

• Anchor Space Optimal Transport: Accelerating Batch Processing of Multiple OT Problems [13.846014191157405]
  We propose a translated OT problem designated as the anchor space optimal transport (ASOT) problem. For the proposed ASOT problem, the distributions will be mapped into a shared anchor point space, which learns the potential common characteristics. Based on the proposed ASOT, the Wasserstein distance error to the original OT problem is proven to be bounded by ground cost errors.
  arXiv  Detail & Related papers  (2023-10-24T18:55:12Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Linear Optimal Partial Transport Embedding [8.23887869467319]
  Optimal transport (OT) has gained popularity due to its various applications in fields such as machine learning, statistics, and signal processing. We propose the Linear partial transport (LOPT) embedding, which extends the (local) linearization technique on OT and HK to the OPT problem.
  arXiv  Detail & Related papers  (2023-02-07T03:28:56Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions. Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem. In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
  arXiv  Detail & Related papers  (2022-11-02T14:35:13Z)
• Proximal Point Imitation Learning [48.50107891696562]
  We develop new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning. We leverage classical tools from optimization, in particular, the proximal-point method (PPM) and dual smoothing. We achieve convincing empirical performance for both linear and neural network function approximation.
  arXiv  Detail & Related papers  (2022-09-22T12:40:21Z)
• Efficient estimates of optimal transport via low-dimensional embeddings [0.0]
  Optimal transport distances (OT) have been widely used in recent work in Machine Learning as ways to compare probability distributions. Recent work by Paty et al., 2019, aims specifically at reducing this cost by computing OT using low-rank projections of the data. We extend this approach and show that one can approximate OT distances by using more general families of maps provided they are 1-Lipschitz.
  arXiv  Detail & Related papers  (2021-11-08T21:22:51Z)
• Unbalanced Optimal Transport through Non-negative Penalized Linear Regression [9.668391961887027]
  We show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem. We propose novel algorithms inspired from inverse problems and nonnegative matrix factorization. We derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties.
  arXiv  Detail & Related papers  (2021-06-08T07:16:37Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Improving Approximate Optimal Transport Distances using Quantization [23.319746583489763]
  Optimal transport is a popular tool in machine learning to compare probability measures geometrically. Linear programming algorithms for computing OT scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access.
  arXiv  Detail & Related papers  (2021-02-25T08:45:06Z)
• Feature Robust Optimal Transport for High-dimensional Data [125.04654605998618]
  We propose feature-robust optimal transport (FROT) for high-dimensional data, which solves high-dimensional OT problems using feature selection to avoid the curse of dimensionality. We show that the FROT algorithm achieves state-of-the-art performance in real-world semantic correspondence datasets.
  arXiv  Detail & Related papers  (2020-05-25T14:07:16Z)

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.