Optimal Transport with Cyclic Symmetry
This work introduces symmetry concepts into OT research, potentially benefiting applications in image processing, urban planning, and graph processing, though it appears incremental as it builds on existing OT formulations.
The authors tackled the problem of speeding up optimal transport (OT) computations by exploiting cyclic symmetry in input data, achieving faster solutions for linear programming OT and entropy-regularized OT on synthetic and real-world datasets.
We propose novel fast algorithms for optimal transport (OT) utilizing a cyclic symmetry structure of input data. Such OT with cyclic symmetry appears universally in various real-world examples: image processing, urban planning, and graph processing. Our main idea is to reduce OT to a small optimization problem that has significantly fewer variables by utilizing cyclic symmetry and various optimization techniques. On the basis of this reduction, our algorithms solve the small optimization problem instead of the original OT. As a result, our algorithms obtain the optimal solution and the objective function value of the original OT faster than solving the original OT directly. In this paper, our focus is on two crucial OT formulations: the linear programming OT (LOT) and the strongly convex-regularized OT, which includes the well-known entropy-regularized OT (EROT). Experiments show the effectiveness of our algorithms for LOT and EROT in synthetic/real-world data that has a strict/approximate cyclic symmetry structure. Through theoretical and experimental results, this paper successfully introduces the concept of symmetry into the OT research field for the first time.