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
- Optimal Transport with Tempered Exponential Measures [33.07787452859956]
We show that a generalization of exponential families with indirect measure normalization gets to a very convenient middle ground.
Our formulation fits naturally in the unbalanced optimal transport problem setting.
arXiv Detail & Related papers (2023-09-07T20:53:23Z) - 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.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.