Paper · Dec 8, 2017

The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations

Robert J. Berman

math.AParXiv:1712.03082v4
View PDF View HTML arXiv page

As on arXiv

Abstract

We show that the discrete Sinkhorn algorithm - as applied in the setting of Optimal Transport on a compact manifold - converges to the solution of a fully non-linear parabolic PDE of Monge-Ampere type, in a large-scale limit. The latter evolution equation has previously appeared in different contexts (e.g. on the torus it can be be identified with the Ricci flow). This leads to algorithmic approximations of the potential of the Optimal Transport map, as well as the Optimal Transport distance, with explicit bounds on the arithmetic complexity of the construction and the approximation errors. As applications we obtain explicit schemes of nearly linear complexity, at each iteration, for optimal transport on the torus and the two-sphere, as well as the far-field antenna problem. Connections to Quasi-Monte Carlo methods are exploited.

View PDF View HTML arXiv page
Submitted
Dec 8, 2017
Last revised
Jun 26, 2020 (v4)
Subjects
math.AP, math.NA

Comments: v3: Major revision; the general exposition has been improved and the main results have been improved for smooth data (Section 5.4). 52 pages v4: This is essentially the version that will appear in Numerische Mathematik

Ricci flowKähler geometryLimit spaces & RCD

Its neighbourhood

Connected papers

The 8 papers on this site closest to this one, judged by the topics they share, the words and phrases in their titles and abstracts, and their authors. They are not its citations, but a map of the work around it. Papers here go back to 2016, plus the canon.

Connected papers This paper in the centre and the 8 papers closest to it around it, in date order clockwise from the top. The closer a paper sits to the centre, the stronger the connection. This paper Stability of solutions to complex Monge-Ampere flows (Vincent Guedj, Hoang Chinh Lu and Ahmed Zeriahi, 2018)6Guedj 2018 Kähler-Ricci Flow preserves negative anti-bisectional curvature (Gabriel Khan and Fangyang Zheng, 2020)4Khan 2020 Optimal Transport and Generalized Ricci Flow (Eva Kopfer and Jeffrey Streets, 2023)2Kopfer 2023 The L^(∞) estimate for parabolic complex Monge-Ampère equations (Qizhi Zhao, 2023)5Zhao 2023 Complex Monge-Ampère equation for positive (p,p)-forms on compact Kähler manifolds (Mathew George, 2024)7George 2024 On a general class of free boundary Monge-Ampère equations (Tristan C. Collins and Benjy Firester, 2025)1Collins 2025 Synthetic approaches to Ricci flows (Matthias Erbar, Marco Flaim, Eric Hupp et al., 2025)8Erbar 2025 Parabolic Monge-Ampère equations on a family of Calabi-Yau manifolds (Jiyuan Han, 2026)3Han 2026
Closer to the centre: more closely connected. Clockwise from the top: oldest to newest. Ricci flowWider flowsalso connected to each other
  1. On a general class of free boundary Monge-Ampère equations

    Tristan C. Collins and Benjy Firester

    Topics Limit spaces & RCD, Kähler geometry · Shared terms “Monge Ampère”, “Ampère equation”, “optimal transport”

  2. Optimal Transport and Generalized Ricci Flow

    Eva Kopfer and Jeffrey Streets

    Topics Limit spaces & RCD · Shared terms “optimal transport”

  3. Parabolic Monge-Ampère equations on a family of Calabi-Yau manifolds

    Jiyuan Han

    Topics Limit spaces & RCD, Kähler geometry · Shared terms “Ampère equation”, “Monge Ampère”

  4. Kähler-Ricci Flow preserves negative anti-bisectional curvature

    Gabriel Khan and Fangyang Zheng

    Topics Limit spaces & RCD, Kähler geometry · Shared terms “optimal transport”

  5. The estimate for parabolic complex Monge-Ampère equations

    Qizhi Zhao

    Topics Kähler geometry · Shared terms “Monge Ampère”, “Ampère equation”

  6. Stability of solutions to complex Monge-Ampere flows

    Vincent Guedj, Hoang Chinh Lu and Ahmed Zeriahi

    Topics Kähler geometry · Shared terms “Monge Ampère”, “Ampère equation”

  7. Complex Monge-Ampère equation for positive -forms on compact Kähler manifolds

    Mathew George

    Topics Kähler geometry · Shared terms “Monge Ampère”, “Ampère equation”, “PDE”

  8. Synthetic approaches to Ricci flows

    Matthias Erbar, Marco Flaim, Eric Hupp et al.

    Topics Limit spaces & RCD · Shared terms “optimal transport”

Read around it

Background reading

The guides for the topics of this paper: what each idea is, why it matters, and the papers to read first.

Ricci flow Hamilton's Ricci flow evolves a Riemannian metric by minus twice its Ricci curvature. It is a nonlinear heat equation for geometry: it spreads… Start with: Three-manifolds with positive Ricci curvature (Hamilton, 1982) Kähler geometry Complex manifolds with compatible Riemannian metrics whose Kähler form is closed. Here Ricci curvature is the complex Hessian of a log-determinant… Start with: On the ricci curvature of a compact kähler manifold and the complex monge‐ampére equation, I (Yau, 1978) Limit spaces & RCD What manifolds look like in the limit when only a lower Ricci bound is kept. Cheeger–Colding theory describes Ricci limit spaces, and RCD spaces… Start with: On the structure of spaces with Ricci curvature bounded below. I (Cheeger et al., 1997)

In the guidebook

  1. 6C.11
    Optimal Transport and Ricci CurvatureBook 6C · Nonlinear PDE: Variational and Geometric Methods

    Kantorovich duality, Wasserstein geometry, the heat equation as a gradient flow of entropy, displacement convexity, and Ricci curvature as convexity, from Lott–Sturm–Villani to McCann–Topping and the reduced volume.

  2. 9B.4
    Convergence of ManifoldsBook 9B · Comparison, Convergence and Heat on Manifolds

    Gromov–Hausdorff and Cheeger–Gromov convergence, and the compactness theorem.

  3. 11B.3
    Compactness of Ricci FlowsBook 11B · Solitons, Compactness and Singularities

    Hamilton’s compactness theorem and the missing injectivity radius bound.