Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
From MaRDI portal
Publication:150668
DOI10.48550/ARXIV.1705.09634arXiv1705.09634MaRDI QIDQ150668FDOQ150668
Authors: Jason Altschuler, Jonathan Weed, Philippe Rigollet 
Publication date: 26 May 2017
Abstract: Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.
Cited In (1)
This page was built for publication: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q150668)
