Optimal Transport with Cyclic Symmetry
Shoichiro Takeda Yasunori Akagi Naoki Marumo Kenta Niwa
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.