pith. sign in

arxiv: 2605.09782 · v2 · pith:Y42FOHJDnew · submitted 2026-05-10 · 💻 cs.DS · stat.ME

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

Krzysztof Choromanski , Derek Long , Ananya Parashar , Dwaipayan Saha This is my paper

Pith reviewed 2026-05-20 22:40 UTC · model grok-4.3

classification 💻 cs.DS stat.ME
keywords Sinkhorn algorithmoptimal transportbounded genus graphsplanar graphsnear-linear timegeodesic distancesseparator decompositionlow displacement rank
0
0 comments X

The pith

GenusSink computes approximate generalized Sinkhorn algorithms in near-linear time and memory for shortest-path costs on bounded-genus graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents GenusSink as a method that accelerates approximate optimal transport computations on graphs of bounded genus, including planar graphs and meshes that approximate 3D surfaces, by replacing brute-force quadratic-time Sinkhorn iterations with separator-based decompositions. It achieves near-linear time for preprocessing, each iteration step, and final transport plan queries while using near-linear memory, through new fast matrix-vector multiplication results that draw on Fourier analysis and low-displacement-rank theory. This matters for any setting where distributions live on manifolds approximated by large graphs and costs are geodesic distances, because the standard approach scales quadratically and quickly becomes impractical. The same machinery yields numerical equivalence to the exact brute-force geodesic Sinkhorn algorithm when the underlying graph has treewidth O(log log n), such as on trees.

Core claim

GenusSink delivers near-linear time preprocessing, near-linear time per iteration, near-linear time for querying the final transport plan matrix, and near-linear memory for approximate generalized Sinkhorn algorithms with shortest-path-distance costs on bounded-genus graphs; it obtains these bounds by combining separator-based graph decompositions with computational-geometry techniques and fast matrix-vector multiplications for generalized distance matrices, and it is numerically equivalent to the brute-force geodesic Sinkhorn algorithm on any n-vertex graph of treewidth O(log log n).

What carries the argument

Separator-based decompositions of bounded-genus graphs that support fast matrix-vector multiplications with generalized distance matrices via Fourier analysis and low-displacement-rank theory, realized through separation graph field integrators (S-GFIs).

If this is right

  • Optimal transport plans with geodesic costs become feasible on large planar meshes and bounded-genus surfaces that arise in 3D modeling.
  • Preprocessing, iteration, and query steps each scale near-linearly instead of quadratically in the number of vertices.
  • Memory usage remains near-linear, removing the quadratic storage bottleneck of dense distance matrices.
  • The algorithm is numerically identical to brute-force geodesic Sinkhorn on any graph of treewidth O(log log n), including all trees.
  • The same separator and fast-multiplication primitives apply to any matrix operation whose entries depend on shortest-path distances on the graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend directly to other minor-closed graph families that admit small separators, such as graphs of bounded treewidth or planar minors.
  • Runtime gains could be measured on real-world road networks or surface meshes to quantify practical speedups beyond worst-case asymptotics.
  • The fast distance-matrix multiplication primitives might be reused for other kernel-based methods that rely on geodesic costs.
  • Convergence guarantees could be tested by comparing iteration counts on high-genus versus low-genus graphs of equal size.

Load-bearing premise

Bounded-genus graphs admit separator decompositions whose treewidth properties let the fast matrix-vector multiplications run without hidden super-linear factors in constants or iteration count.

What would settle it

Measure wall-clock time for preprocessing plus a fixed number of iterations on a family of planar graphs whose vertex count increases by successive factors of two; the observed scaling deviates from linear if super-linear factors are present.

Figures

Figures reproduced from arXiv: 2605.09782 by Ananya Parashar, Derek Long, Dwaipayan Saha, Krzysztof Choromanski.

Figure 1
Figure 1. Figure 1: Left: Seven-vertex planar graph. Right: A pictorial description of its treewidth decomposition, with the treewidth parameter upper-bounding the sizes of the clusters of nodes above (that we will refer to as bags, see: Sec. 2.1). Two graph pieces, obtained with the separator {B, C, D}, are highlighted via red dashed boxes. The treewidth decomposition provides a gateway for designing efficient algorithms for… view at source ↗
Figure 2
Figure 2. Figure 2: Left to right: 2D-surfaces of 3D objects with genus values: 0, 1, 2 and 3. In this paper, we are especially interested in families of graphs with bounded genus that can be used in particular to provide discretized mesh representations of the above surfaces. distributions defined on the manifolds approximated by weighted graphs and with cost functions given by geodesic distances. We conduct rigorous theoret… view at source ↗
Figure 3
Figure 3. Figure 3: Left: The pictorial representation of the S-GFI data structure. In that example, the corresponding tree has a root with two children and four grandchildren. Right: The visualization of the cross_compute function with the medians depicted in red/green and their corresponding splits highlighted as dashed lines. ξi = X j∈RB f(ai [k] + bj [k])I[wk i ≺ z k j ]vj (11) We can then continue the calculations recurs… view at source ↗
Figure 4
Figure 4. Figure 4: ). In contrast, most approximate baselines exhibit a clear accuracy gap. 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 2 10 1 10 0 1… view at source ↗
Figure 5
Figure 5. Figure 5: Left: examples of Thingi10K meshes. Middle: absolute OT-cost error relative to dense geodesic Sinkhorn for several efficient Sinkhorn methods. As before, GenusSink stays numerically exact while providing significant computational gains. Right: runtime scaling for dense geodesic kernel construction versus two most accurate efficient methods: GenusSink and Greenkhorn (see: left), with error bars over repeate… view at source ↗
Figure 6
Figure 6. Figure 6: Bronx road graph (left), mean response times across different Sinkhorn methods (middle), and tail response time gaps relative to GenusSink at quantiles from 0.95 onwards (right). 5 Conclusion We proposed in this paper GenusSink, a new class of efficient Sinkhorn algorithms operating on graph metric spaces for bounded genus graphs and characterized by near-linear time (1) pre-processing, (2) iteration step,… view at source ↗
Figure 7
Figure 7. Figure 7: Planar dumbbell graphs after the root separator split. The two lobes form the left and right subgraphs, while the narrow bridge induces a small separator; the examples above correspond to two different handle widths. w ∈ {1, 2, 3}, and initial/target distributions given by two-component Gaussian mixtures localized on the left and right lobes, respectively, and normalized over the graph vertices. The entrop… view at source ↗
Figure 8
Figure 8. Figure 8: Planar dumbbell experiments for handle widths w = 1, 2, 3 (left to right). Top: absolute Sinkhorn￾cost error relative to the dense geodesic full-kernel baseline. Bottom: total runtime for the baseline and two most accurate efficient methods: Sparse Sinkhorn and GenusSink. Across all widths, GenusSink remains numerically exact while providing significant computational gains. In addition to the dumbbell grap… view at source ↗
Figure 9
Figure 9. Figure 9: Pseudo-genus surface family used in our synthetic experiments. We show planar sphere-topology surface meshes embedded in R 3 for pseudo-genus orders 1, 2, and 3, colored according to the root separator split used to initialize the separation tree. mixtures in the surface parameter coordinates and normalized over the graph vertices. We again compare GenusSink against the dense geodesic full-kernel Sinkhorn … view at source ↗
read the original abstract

We present GenusSink, a new class of approximate generalized Sinkhorn algorithms with shortest-path-distance costs for bounded genus (e.g. planar) graphs, providing near-linear time: (1) pre-processing, (2) iteration step, (3) final transport plan matrix querying and near-linear memory. Graphs handled by GenusSink include in particular planar graphs and bounded-genus meshes approximating 3D objects. GenusSink addresses total quadratic time complexity of its brute-force counterpart by leveraging separator-based decomposition of graphs, computational geometry techniques, and new results on fast matrix-vector multiplications with generalized distance matrices, using, in particular, Fourier analysis and low displacement rank theory. It is inspired by recent breakthroughs in graph theory on approximating bounded genus metrics with small treewidth metrics \citep{minor-free-paper}. The graph-centric approach enables us to target optimal transport problem with the corresponding distributions defined on the manifolds approximated by weighted graphs and with cost functions given by geodesic distances. We conduct rigorous theoretical analysis of GenusSink, provide practical implementations, leveraging newly introduced in this paper \textit{separation graph field integrators} (S-GFIs) data structures and present empirical verification. GenusSink provides orders of magnitude more accurate computations than other efficient Sinkhorn algorithms, while still guaranteeing significant computational improvements, as compared to the baseline. As a by-product of the developed methods, we show that GenusSink is \textbf{numerically equivalent} to the brute-force geodesic Sinkhorn algorithm on $n$-vertex graphs with treewidth $O(\log \log (n))$ (e.g. on trees).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces GenusSink, a new class of approximate generalized Sinkhorn algorithms for shortest-path-distance costs on bounded-genus graphs (including planar graphs and meshes). It claims near-linear time for preprocessing, each iteration step, and final transport-plan querying, together with near-linear memory, by combining separator-based decompositions, Fourier analysis, and low-displacement-rank matrix-vector multiplication. The approach is inspired by metric approximations of bounded-genus graphs by small-treewidth graphs; the manuscript supplies theoretical analysis, implementations based on newly introduced separation graph field integrators (S-GFIs), empirical comparisons, and a by-product showing numerical equivalence to brute-force geodesic Sinkhorn on graphs of treewidth O(log log n).

Significance. If the near-linear runtime claims are substantiated, the result would be a meaningful contribution to scalable optimal transport on geometric graphs, enabling efficient geodesic OT on planar and bounded-genus meshes that arise in computational geometry and 3-D modeling. The synthesis of graph separators with structured linear-algebra techniques, together with the low-treewidth equivalence result, offers both algorithmic and practical value.

major comments (2)
  1. [Theoretical analysis of fast matrix-vector multiplication] The central near-linear per-iteration claim rests on fast matrix-vector multiplication for generalized distance matrices via separator decompositions and low-displacement-rank structure. Bounded-genus graphs admit balanced separators of size Θ(√(g n)); the recursive hierarchy therefore risks displacement ranks or Fourier-mode counts that scale with separator size or depth, potentially yielding Ω(n^{3/2}) rather than O(n polylog n) multiplication cost. The manuscript must supply an explicit rank bound independent of n and g (or a concrete recurrence showing the total cost remains near-linear) to support the headline runtime.
  2. [Rigorous theoretical analysis] The abstract and description assert 'rigorous theoretical analysis' together with error bounds and iteration counts, yet no derivation details, explicit convergence rates, or dependence of iteration count on the approximation parameters are visible. Because the overall near-linear guarantee is the product of per-iteration cost and iteration count, this omission is load-bearing for the main claim.
minor comments (2)
  1. [Abstract] The placeholder citation 'minor-free-paper' should be expanded to a full bibliographic entry.
  2. [Implementation and data structures] Clarify the precise definition and construction of the separation graph field integrators (S-GFIs) data structure, including space and query-time bounds, so that the near-linear memory claim can be verified independently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments on the matrix-vector multiplication analysis and the presentation of convergence guarantees are well-taken. Below we respond point by point, clarifying the existing arguments while agreeing that additional explicit bounds and derivations will improve the manuscript. We will revise accordingly.

read point-by-point responses

  1. Referee: [Theoretical analysis of fast matrix-vector multiplication] The central near-linear per-iteration claim rests on fast matrix-vector multiplication for generalized distance matrices via separator decompositions and low-displacement-rank structure. Bounded-genus graphs admit balanced separators of size Θ(√(g n)); the recursive hierarchy therefore risks displacement ranks or Fourier-mode counts that scale with separator size or depth, potentially yielding Ω(n^{3/2}) rather than O(n polylog n) multiplication cost. The manuscript must supply an explicit rank bound independent of n and g (or a concrete recurrence showing the total cost remains near-linear) to support the headline runtime.

    Authors: We appreciate this observation on the complexity of the recursive separator hierarchy. The analysis in the manuscript relies on the low-displacement-rank property of the generalized distance matrices induced by the S-GFI data structures, combined with the fact that bounded-genus metrics admit approximations by O(log log n)-treewidth graphs (as cited). This keeps the effective rank and Fourier mode count bounded by a function of g and the approximation parameter rather than growing with separator size at every level. Nevertheless, we agree that an explicit recurrence and rank bound would make the near-linear claim fully transparent. In the revision we will insert a new subsection deriving the recurrence T(n) = 2T(n/2) + O(r(g,δ) √n log n) where r(g,δ) is the displacement rank (independent of n), showing that the total cost remains O(n polylog n) with constants depending only on genus and accuracy parameters. revision: yes

  2. Referee: [Rigorous theoretical analysis] The abstract and description assert 'rigorous theoretical analysis' together with error bounds and iteration counts, yet no derivation details, explicit convergence rates, or dependence of iteration count on the approximation parameters are visible. Because the overall near-linear guarantee is the product of per-iteration cost and iteration count, this omission is load-bearing for the main claim.

    Authors: The manuscript contains the core convergence analysis in Sections 3.2 and 4.2, where we bound the approximation error of the generalized distance matrix by the treewidth approximation parameter δ and then invoke standard Sinkhorn convergence results under additive cost perturbations. The number of iterations is shown to be O((1/ε) log(1/δ)) for accuracy ε. We acknowledge, however, that the derivations are condensed and the dependence on δ is not stated as a single displayed equation. In the revised version we will expand these sections with the full step-by-step derivation of the iteration bound and an explicit statement of how the per-iteration near-linear cost multiplies with the iteration count to yield the overall guarantee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims build on external graph-theoretic results

full rationale

The paper's derivation relies on separator-based decompositions of bounded-genus graphs, Fourier analysis, low-displacement-rank theory for fast matrix-vector multiplications, and an external citation to prior work on approximating bounded-genus metrics by small-treewidth metrics. The by-product numerical equivalence claim for O(log log n) treewidth graphs is presented as a derived consequence rather than an input definition. No quoted equations or steps reduce a claimed runtime or prediction to a fitted parameter, self-definition, or load-bearing self-citation chain. The method is self-contained against external benchmarks in graph theory and structured linear algebra, with no evident reduction of the near-linear bounds to internal construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of efficient separators for bounded-genus graphs and on the applicability of low-displacement-rank and Fourier techniques to generalized distance matrices; these are treated as established or newly derived but are not unpacked in the abstract.

axioms (1)
  • domain assumption Bounded-genus graphs admit separator decompositions that reduce the problem to low-treewidth subproblems whose distance matrices have low displacement rank.
    Invoked when claiming near-linear matrix-vector multiplies; location: abstract paragraph on leveraging separator-based decomposition.

pith-pipeline@v0.9.0 · 5829 in / 1482 out tokens · 24158 ms · 2026-05-20T22:40:58.792814+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · 2 internal anchors

  1. [1]

    Alaya, Maxime Bérar, Gilles Gasso, and Alain Rakotomamonjy

    Mokhtar Z. Alaya, Maxime Bérar, Gilles Gasso, and Alain Rakotomamonjy. Screening sinkhorn algorithm for regularized optimal transport. InAdvances in Neural Information Processing Systems, volume 32, 2019

    work page 2019

  2. [2]

    Altschuler, Jonathan Weed, and Philippe Rigollet

    Jason M. Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approxima- tion algorithms for optimal transport via sinkhorn iteration. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V . N. Vishwanathan, and Roman Garnett, editors,Advances in Neural Information Processing Systems 30: Annual Conference on ...

    work page 2017

  3. [3]

    Information geometry for regularized optimal transport and barycenters of patterns.Neural Comput., 31(5):827–848,

    Shun-ichi Amari, Ryo Karakida, Masafumi Oizumi, and Marco Cuturi. Information geometry for regularized optimal transport and barycenters of patterns.Neural Comput., 31(5):827–848,

    work page

  4. [4]

    2011, Neural Comput., 23, 1661, 10.1162/NECO\_a\_00142

    doi: 10.1162/NECO\_A\_01178. URLhttps://doi.org/10.1162/neco_a_01178

    work page doi:10.1162/neco

  5. [5]

    Lectures on optimal transport.UNITEXT,

    Luigi Ambrosio, Elia Brué, and Daniele Semola. Lectures on optimal transport.UNITEXT,

    work page

  6. [6]

    URLhttps://api.semanticscholar.org/CorpusID:244769124

    work page

  7. [7]

    Wasserstein generative adversarial networks

    Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Proceedings of Machine Learning Research, pages 214–223. PMLR, 2017. URL http:// proceedings.ml...

    work page 2017

  8. [8]

    Bodlaender

    Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, 1993. URL https://api.semanticscholar.org/CorpusID:2028181

    work page 1993

  9. [9]

    Fast tree-field integrators: From low displacement rank to topological transformers

    Krzysztof Marcin Choromanski, Arijit Sehanobish, Somnath Basu Roy Chowdhury, Han Lin, Kumar Avinava Dubey, Tamás Sarlós, and Snigdha Chaturvedi. Fast tree-field integrators: From low displacement rank to topological transformers. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, edi- tors,A...

    work page 2024

  10. [10]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms, 3rd Edition. MIT Press, 2009. ISBN 978-0-262-03384-8. URL http://mitpress. mit.edu/books/introduction-algorithms

    work page 2009

  11. [11]

    Sinkhorn distances: Lightspeed computation of optimal transport

    Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors,Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Taho...

    work page 2013

  12. [12]

    Differentiable ranking and sort- ing using optimal transport

    Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sort- ing using optimal transport. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors,Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, ...

    work page 2019

  13. [13]

    6 Josep Díaz, Olli Pottonen, Maria J

    Marek Cygan, Fedor V . Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015. ISBN 978-3-319-21274-6. doi: 10.1007/978-3-319-21275-3. URL https://doi.org/10. 1007/978-3-319-21275-3. 10

    work page doi:10.1007/978-3-319-21275-3 2015

  14. [14]

    Springer, 2012

    Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer, 2012. ISBN 978-3-642-14278-9

    work page 2012

  15. [15]

    The optimal partial transport problem.Archive for Rational Mechanics and Analysis, 195:533–560, 2010

    Alessio Figalli. The optimal partial transport problem.Archive for Rational Mechanics and Analysis, 195:533–560, 2010. URL https://api.semanticscholar.org/CorpusID: 15899562

    work page 2010

  16. [16]

    Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

    Arnold Filtser and Hung Le. Low treewidth embeddings of planar and minor-free metrics. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 1081–1092. IEEE, 2022. doi: 10.1109/ FOCS54457.2022.00105. URLhttps://doi.org/10.1109/FOCS54457.2022.00105

    work page doi:10.1109/focs54457.2022.00105 2022

  17. [17]

    Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya-Polo, and Tomaso A. Poggio. Learning with a wasserstein loss. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors,Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2...

    work page 2015

  18. [18]

    Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis R. Bach. Stochastic optimization for large-scale optimal transport. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors,Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5- 10, ...

    work page 2016

  19. [19]

    Courville

    Ishaan Gulrajani, Faruk Ahmed, Martín Arjovsky, Vincent Dumoulin, and Aaron C. Courville. Improved training of wasserstein gans. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V . N. Vishwanathan, and Roman Garnett, edi- tors,Advances in Neural Information Processing Systems 30: Annual Conference on Neu- ral Informati...

    work page 2017

  20. [20]

    Tape, Guy Wolf, and Smita Krishnaswamy

    Guillaume Huguet, Alexander Tong, María Ramos Zapatero, Christopher J. Tape, Guy Wolf, and Smita Krishnaswamy. Geodesic sinkhorn for fast and accurate optimal transport on manifolds. In2023 IEEE 33rd International Workshop on Machine Learning for Signal Processing (MLSP), pages 1–6. IEEE, 2023

    work page 2023

  21. [21]

    Weiss, Gianluca Janka, Ann M

    Tomasz Kacprzak, Francois Kamper, Michael W. Weiss, Gianluca Janka, Ann M. Dillner, and Satoshi Takahama. Scalable approximate algorithms for optimal transport linear mod- els.ArXiv, abs/2504.04609, 2025. URL https://api.semanticscholar.org/CorpusID: 277621015

    work page arXiv 2025

  22. [22]

    Kelvin Kan, Xingjian Li, and Stanley J. Osher. Ot-transformer: A continuous-time transformer architecture with optimal transport regularization.CoRR, abs/2501.18793, 2025. doi: 10.48550/ ARXIV .2501.18793. URLhttps://doi.org/10.48550/arXiv.2501.18793

    work page doi:10.48550/arxiv.2501.18793 2025

  23. [23]

    Kantorovitch

    L. Kantorovitch. On the translocation of masses.Management Science, 5:1–4, 1958. URL https://api.semanticscholar.org/CorpusID:214798034

    work page 1958

  24. [24]

    Metric learning in optimal transport for domain adaptation

    Tanguy Kerdoncuff, Rémi Emonet, and Marc Sebban. Metric learning in optimal transport for domain adaptation. In Christian Bessiere, editor,Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 2162–2168. ijcai.org, 2020. doi: 10.24963/IJCAI.2020/299. URLhttps://doi.org/10.24963/ijcai.2020/299

    work page doi:10.24963/ijcai.2020/299 2020

  25. [25]

    Kolkin, Jason Salavon, and Gregory Shakhnarovich

    Nicholas I. Kolkin, Jason Salavon, and Gregory Shakhnarovich. Style transfer by relaxed optimal transport and self-similarity. InIEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 10051–10060. Computer Vision Foundation / IEEE, 2019. doi: 10.1109/CVPR.2019.01029

    work page doi:10.1109/cvpr.2019.01029 2019

  26. [26]

    Importance sparsification for sinkhorn algo- rithm.J

    Mengyu Li, Jun Yu, Tao Li, and Cheng Meng. Importance sparsification for sinkhorn algo- rithm.J. Mach. Learn. Res., 24:247:1–247:44, 2023. URL https://jmlr.org/papers/ v24/22-1311.html. 11

    work page 2023

  27. [27]

    Recent advances in optimal transport for machine learning, 2024

    Eduardo Fernandes Montesuma, Fred Ngolè Mboula, and Antoine Souloumiac. Recent advances in optimal transport for machine learning, 2024. URL https://arxiv.org/abs/2306. 16156

    work page 2024

  28. [28]

    Cambridge University Press, 2014

    Yann Ollivier, Herve Pajot, and Cédric Villani, editors.Optimal Transport - Theory and Applications, volume 413 ofLondon Mathematical Society lec- ture note series. Cambridge University Press, 2014. ISBN 978-1-10-768949-

    work page 2014

  29. [29]

    URL http://www.cambridge.org/de/academic/subjects/mathematics/ geometry-and-topology/optimal-transport-theory-and-applications

    work page

  30. [30]

    Hadi Amini

    Luiz Manella Pereira and M. Hadi Amini. A survey on optimal transport for machine learning: Theory and applications.IEEE Access, 13:26506–26526, 2025. doi: 10.1109/ACCESS.2025. 3539926. URLhttps://doi.org/10.1109/ACCESS.2025.3539926

    work page doi:10.1109/access.2025 2025

  31. [31]

    Dickerson

    Gabriel Peyré. Optimal transport for machine learners.CoRR, abs/2505.06589, 2025. doi: 10.48550/ARXIV .2505.06589. URLhttps://doi.org/10.48550/arXiv.2505.06589

    work page internal anchor Pith review doi:10.48550/arxiv 2025

  32. [32]

    Computational Optimal Transport: With Ap- plications to Data Science

    Gabriel Peyré and Marco Cuturi. Computational optimal transport.Found. Trends Mach. Learn., 11(5-6):355–607, 2019. doi: 10.1561/2200000073. URL https://doi.org/10. 1561/2200000073

    work page doi:10.1561/2200000073 2019

  33. [33]

    Gromov-wasserstein averaging of kernel and distance matrices

    Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In Maria-Florina Balcan and Kilian Q. Weinberger, editors,Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, JMLR Workshop and Conference Proceedings, pages 2664–2672. JMLR.org,

    work page 2016

  34. [34]

    URLhttp://proceedings.mlr.press/v48/peyre16.html

    work page

  35. [35]

    Wasserstein barycenter and its application to texture mixing

    Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. Wasserstein barycenter and its application to texture mixing. In Alfred M. Bruckstein, Bart M. ter Haar Romeny, Alexander M. Bronstein, and Michael M. Bronstein, editors,Scale Space and Variational Methods in Computer Vision - Third International Conference, SSVM 2011, Ein-Gedi, Is- rael, May 29 -...

    work page doi:10.1007/978-3-642-24785-9 2011

  36. [36]

    Mason, and Andrea Raith

    Samuel Ridler, Andrew J. Mason, and Andrea Raith. A simulation and optimisation package for emergency medical services.European Journal of Operational Research, 298(3):1101– 1113, 2022. ISSN 0377-2217. doi: https://doi.org/10.1016/j.ejor.2021.07.038. URL https: //www.sciencedirect.com/science/article/pii/S0377221721006330

    work page doi:10.1016/j.ejor.2021.07.038 2022

  37. [37]

    Tim Salimans, Han Zhang, Alec Radford, and Dimitris N. Metaxas. Improving gans using optimal transport. In6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenRe- view.net, 2018. URLhttps://openreview.net/forum?id=rkQkBnJAb

    work page 2018

  38. [38]

    Linear time sinkhorn divergences using positive features

    Meyer Scetbon and Marco Cuturi. Linear time sinkhorn divergences using positive features. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors,Advances in Neural Information Processing Systems, volume 33, pages 13468–13480. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/ 9bde76f262285bb1...

    work page 2020

  39. [39]

    Stabilized sparse scaling algorithms for entropy regularized transport problems.SIAM Journal on Scientific Computing, 41(3):A1443–A1481, 2019

    Bernhard Schmitzer. Stabilized sparse scaling algorithms for entropy regularized transport problems.SIAM Journal on Scientific Computing, 41(3):A1443–A1481, 2019. doi: 10.1137/ 16M1106018

    work page 2019

  40. [40]

    Espformer: Doubly-stochastic attention with expected sliced transport plans

    Ashkan Shahbazi, Elaheh Akbari, Darian Salehi, Xinran Liu, Navid Naderializadeh, and Soheil Kolouri. Espformer: Doubly-stochastic attention with expected sliced transport plans. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors,Forty-second International Conference on Mac...

    work page 2025

  41. [41]

    Sainath, and Sanjiv Kumar

    Vikas Sindhwani, Tara N. Sainath, and Sanjiv Kumar. Structured transforms for small-footprint deep learning. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors,Advances in Neural Information Processing Systems 28: Annual Confer- ence on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal,...

    work page 2015

  42. [42]

    Accelerating sinkhorn algorithm with sparse newton iterations

    Xun Tang, Michael Shavlovsky, Holakou Rahmanian, Elisa Tardini, Kiran Koshy Thekumpara- mpil, Tesi Xiao, and Lexing Ying. Accelerating sinkhorn algorithm with sparse newton iterations. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https://openreview.net/forum? id=K...

    work page 2024

  43. [43]

    Optimal transport for structured data with application on graphs

    Titouan Vayer, Nicolas Courty, Romain Tavenard, Laetitia Chapel, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Lea...

    work page 2019

  44. [44]

    Gromov-wasserstein learning for graph matching and node embedding

    Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov-wasserstein learning for graph matching and node embedding. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9- 15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, pages 6...

    work page 2019

  45. [45]

    Thingi10K: A Dataset of 10,000 3D-Printing Models

    Qingnan Zhou and Alec Jacobson. Thingi10k: A dataset of 10,000 3d-printing models.arXiv preprint arXiv:1605.04797, 2016. A Efficient computation of cross_compute for|S|= 1and generalf The problem of computing efficientlycross_computeis equivalent to the problem of the efficient (near-linear) multiplication with matrices M= [f(x i +y j)]j=1,...,|B| i=1,......

    work page internal anchor Pith review Pith/arXiv arXiv 2016