# Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds

arXiv: https://arxiv.org/abs/2211.00805 · HTML: https://mlsanity.com/paper/2211.00805/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 2 Nov 2022.

## Builds on (most cited first, 11 of 11)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics](https://mlsanity.com/paper/2002.04461/) (2020)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Manifold Interpolating Optimal-Transport Flows for Trajectory Inference](https://mlsanity.com/paper/2206.14928/) (2022)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Ground Metric Learning on Graphs](https://mlsanity.com/paper/1911.03117/) (2019)
- [Fast Polynomial Approximation of Heat Kernel Convolution on Manifolds and Its Application to Brain Sulcal and Gyral Graph Pattern Analysis](https://mlsanity.com/paper/1911.02721/) (2019)
- [Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance](https://mlsanity.com/paper/2107.12334/) (2021)
- [Fast Multiscale Diffusion on Graphs](https://mlsanity.com/paper/2104.14652/) (2021)

## Built on by (most cited first, 10 of 10)

- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Model alignment using inter-modal bridges](https://mlsanity.com/paper/2505.12322/) (2025)
- [Linearized Optimal Transport for Analysis of High-Dimensional Point-Cloud and Single-Cell Data](https://mlsanity.com/paper/2510.22033/) (2025)
- [Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps](https://mlsanity.com/paper/2412.13372/) (2024)
- [Reliable Modeling of Distribution Shifts via Displacement-Reshaped Optimal Transport](https://mlsanity.com/paper/2605.04965/) (2026)
- [Pheno-GS: Phenoscape-scale Geodesic Sinkhorn](https://mlsanity.com/paper/2609.27633/) (2026)
- [Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control](https://mlsanity.com/paper/2610.02195/) (2026)

## Abstract (arXiv)

Efficient computation of optimal transport distance between distributions is of growing importance in data science. Sinkhorn-based methods are currently the state-of-the-art for such computations, but require O(n2) computations. In addition, Sinkhorn-based methods commonly use an Euclidean ground distance between datapoints. However, with the prevalence of manifold structured scientific data, it is often desirable to consider geodesic ground distance. Here, we tackle both issues by proposing Geodesic Sinkhorn -- based on diffusing a heat kernel on a manifold graph. Notably, Geodesic Sinkhorn requires only O(nlog n) computation, as we approximate the heat kernel with Chebyshev polynomials based on the sparse graph Laplacian. We apply our method to the computation of barycenters of several distributions of high dimensional single cell data from patient samples undergoing chemotherapy. In particular, we define the barycentric distance as the distance between two such barycenters. Using this definition, we identify an optimal transport distance and path associated with the effect of treatment on cellular data.