Fast Sinkhorn. I: An O(N) algorithm for the Wasserstein-1 metric

DOI10.4310/CMS.2022.V20.N7.A11zbMATH Open1503.49027arXiv2202.10042MaRDI QIDQ2103082FDOQ2103082

Authors: Qichen Liao, Jing Chen, Zihao Wang, Bo Bai, Hao Wu, Shi Jin 

Publication date: 13 December 2022

Published in: Communications in Mathematical Sciences (Search for Journal in Brave)

Abstract: The Wasserstein metric is broadly used in optimal transport for comparing two probabilistic distributions, with successful applications in various fields such as machine learning, signal processing, seismic inversion, etc. Nevertheless, the high computational complexity is an obstacle for its practical applications. The Sinkhorn algorithm, one of the main methods in computing the Wasserstein metric, solves an entropy regularized minimizing problem, which allows arbitrary approximations to the Wasserstein metric with O(N^2) computational cost. However, higher accuracy of its numerical approximation requires more Sinkhorn iterations with repeated matrix-vector multiplications, which is still unaffordable. In this work, we propose an efficient implementation of the Sinkhorn algorithm to calculate the Wasserstein-1 metric with O(N) computational cost, which achieves the optimal theoretical complexity. By utilizing the special structure of Sinkhorn's kernel, the repeated matrix-vector multiplications can be implemented with O(N) times multiplications and additions, using the Qin Jiushao or Horner's method for efficient polynomial evaluation, leading to an efficient algorithm without losing accuracy. In addition, the log-domain stabilization technique, used to stabilize the iterative procedure, can also be applied in this algorithm. Our numerical experiments show that the newly developed algorithm is one to three orders of magnitude faster than the original Sinkhorn algorithm.

Full work available at URL: https://arxiv.org/abs/2202.10042

Recommendations

• Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
• Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm
• Optimal transport: fast probabilistic approximation with exact solvers
• The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations
• A stable alternative to Sinkhorn's algorithm for regularized optimal transport

zbMATH Keywords

fast algorithmoptimal transportsinkhorn algorithmFS-1 algorithmWasserstein-1 metric

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Optimal transportation (49Q22) Discrete approximations in optimal control (49M25)

Cited In (6)

• Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
• Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm
• A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
• On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
• Fast sinkhorn. II: Collinear triangular matrix and linear time accurate computation of optimal transport
• The Wasserstein metric matrix and its computational property

This page was built for publication: Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2103082)