Optimal Transport with Symmetry Groups

摘要

We propose a novel algorithm that accelerates optimal transport by exploiting intrinsic symmetries induced by finite group actions. The core of our approach is to recover the orbit decomposition and the associated algebraic structure directly from the cost matrix—without requiring prior knowledge of the group—and to reduce the original transport problem to a substantially smaller problem on the orbit space. This reduction preserves optimality while achieving a significant drop in computational complexity. We develop efficient solvers for two central classes of optimal transport: linear OT and entropy‑regularized OT. Experiments on synthetic data and real‑world image datasets confirm the efficiency and robustness of the method. To our knowledge, this work is the first to systematically incorporate symmetry groups into optimal transport, providing both a theoretical framework and a practical pathway to computational acceleration.