2022/11/02 by Guillaume Huguet, Huguet, Guillaume, Alexander Tong +8 · 1 citation
Computer Science · Mathematics · #FOS: Biological sciences #FOS: Computer and information sciences #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Quantitative Methods (q-bio.QM) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2211.00805
openalex publication_date 2022/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.