A Memory-Efficient Hierarchical Algorithm for Large-scale Optimal Transport Problems

摘要

We propose HALO, a memory-efficient hierarchical algorithm for solving large-scale optimal transport (OT) problems with squared Euclidean cost, particularly effective in moderate-dimensional settings. The core of \ours lies in combining a hierarchical representation of the OT problem with parallel-friendly linear programming solvers, within which an active pruning technique is integrated to further reduce memory usage and computational cost. Theoretically, we establish a scale-independent iteration-complexity upper bound for the refinement phase, which is consistent with our numerical observations. Numerically, experiments on the image dataset \dataset and the 3D point cloud dataset \datasetnongrid demonstrate that \ours effectively alleviates the memory and scalability bottlenecks of existing solvers. Our method demonstrates significant advantages compared to state-of-the-art baselines: for images with $n=1024^2$ pixels, it achieves an $8.9\times$ speedup and $70.5$% reduction in memory usage under comparable accuracy; for 3D point clouds at scale $n=2^{18}$, it achieves a $1.84\times$ speedup and an $83.2$% reduction in memory usage with $24.9$% lower transport cost.