Optimal Transport with Cyclic Symmetry
- URL: http://arxiv.org/abs/2311.13147v1
- Date: Wed, 22 Nov 2023 04:18:23 GMT
- Title: Optimal Transport with Cyclic Symmetry
- Authors: Shoichiro Takeda, Yasunori Akagi, Naoki Marumo, Kenta Niwa
- Abstract summary: We propose novel fast algorithms for optimal transport (OT) utilizing a cyclic symmetry structure of input data.
This paper successfully introduces the concept of symmetry into the OT research field for the first time.
- Score: 14.140178595218625
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose novel fast algorithms for optimal transport (OT) utilizing a
cyclic symmetry structure of input data. Such OT with cyclic symmetry appears
universally in various real-world examples: image processing, urban planning,
and graph processing. Our main idea is to reduce OT to a small optimization
problem that has significantly fewer variables by utilizing cyclic symmetry and
various optimization techniques. On the basis of this reduction, our algorithms
solve the small optimization problem instead of the original OT. As a result,
our algorithms obtain the optimal solution and the objective function value of
the original OT faster than solving the original OT directly. In this paper,
our focus is on two crucial OT formulations: the linear programming OT (LOT)
and the strongly convex-regularized OT, which includes the well-known
entropy-regularized OT (EROT). Experiments show the effectiveness of our
algorithms for LOT and EROT in synthetic/real-world data that has a
strict/approximate cyclic symmetry structure. Through theoretical and
experimental results, this paper successfully introduces the concept of
symmetry into the OT research field for the first time.
Related papers
- Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions.
Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
arXiv Detail & Related papers (2023-10-02T11:24:36Z) - Unbalanced Optimal Transport meets Sliced-Wasserstein [11.44982599214965]
We propose two new loss functions based on the idea of slicing unbalanced OT, and study their induced topology and statistical properties.
We show that the resulting methodology is modular as it encompasses and extends prior related work.
arXiv Detail & Related papers (2023-06-12T15:15:00Z) - 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) - 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) - 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) - 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) - Efficient Robust Optimal Transport with Application to Multi-Label
Classification [12.521494095948068]
We model the feature-feature relationship via a symmetric positive semi-definite Mahalanobis metric in the OT cost function.
We view the resulting optimization problem as a non-linear OT problem, which we solve using the Frank-Wolfe algorithm.
Empirical results on the discriminative learning setting, such as tag prediction and multi-class classification, illustrate the good performance of our approach.
arXiv Detail & Related papers (2020-10-22T16:43:52Z) - Learning Cost Functions for Optimal Transport [44.64193016158591]
Inverse optimal transport (OT) refers to the problem of learning the cost function for OT from observed transport plan or its samples.
We derive an unconstrained convex optimization formulation of the inverse OT problem, which can be further augmented by any customizable regularization.
arXiv Detail & Related papers (2020-02-22T07:27:17Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
Adaptivity is an important yet under-studied property in modern optimization theory.
Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
arXiv Detail & Related papers (2020-02-13T05:42:27Z)
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.