Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds
This addresses the need for faster and more accurate optimal transport methods for manifold-structured data in scientific applications like single-cell analysis.
The paper tackles the problem of efficiently computing optimal transport distances on manifolds by proposing Geodesic Sinkhorn, which reduces computation from O(n^2) to O(n log n) and uses geodesic distances instead of Euclidean ones, applied to single-cell data to identify treatment effects.
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(n^2)$ 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(n\log 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.