Related papers: Approximating Optimal Transport via Low-rank and Sparse Factorization

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

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)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z)
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)
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)
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)
FLOT: Scene Flow on Point Clouds Guided by Optimal Transport [82.86743909483312]
We propose and study a method called FLOT that estimates scene flow on point clouds. Inspired by recent works on graph matching, we build a method to find these correspondences by borrowing tools from optimal transport. Our main finding is that FLOT can perform as well as the best existing methods on synthetic and real-world datasets.
arXiv Detail & Related papers (2020-07-22T00:15:30Z)

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