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.

我们提出了利用输入数据的周期对称结构的新型快速最优传输算法，通过利用周期对称性和各种优化技术，将传输优化问题简化为具有更少变量的小型优化问题，从而更快地获得原始最优输运问题的最优解和目标函数值。在这篇论文中，我们主要关注两个关键的传输优化问题：线性规划传输优化问题（LOT）和强凸正则化传输优化问题，其中包括著名的熵正则化传输优化问题（EROT）。实验证明了我们的算法在具有严格/近似周期对称结构的合成/真实世界数据上的有效性。通过理论和实验结果，本文首次成功将对称性概念引入传输优化研究领域。

具有循环对称性的最优输运