Sparsification Techniques for Large‐Scale Optimal Transport Problems

ABSTRACT Optimal transport (OT) methods and their variants have become increasingly prominent tools in computer science and machine learning, owing to their appealing geometric properties and powerful potency. Despite broad applications, OT methods suffer from prohibitively high computational cost, limiting the scalability even for moderately sized datasets. To address this challenge, regularized OT formulations and the corresponding Sinkhorn algorithm have emerged as standard alternatives to improve efficiency. However, these methods still face the high per‐iteration cost and slow convergence rate drawbacks. Sparsification techniques have emerged as an effective and practically valuable class of methods for mitigating these computational bottlenecks by leveraging inherent or induced sparsity in the matrices involved in OT optimization. Broadly, sparsification methods can be grouped into two main categories: (1) kernel‐based sparsification building on the primal regularized OT formulation, and (2) Hessian‐based sparsification, derived from the dual formulation. In this survey, we provide an extensive and comprehensive review of sparsification techniques developed for OT problems, highlighting their underlying motivations, algorithmic distinctions, and theoretical guarantees. This article is categorized under: Statistical and Graphical Methods of Data Analysis > Sampling Algorithms and Computational Methods > Computational Complexity