Gromov–Wasserstein Problem with Cyclic Symmetry

We propose novel fast algorithms for the Gromov–Wasserstein problem (GW) using cyclic symmetry of input data. Such GW with cyclic symmetry naturally appears as an object matching task underlying various real-world computer vision applications, e.g., image registration, point cloud registration, stereo matching, and 3D reconstruction. Gradient-based algorithms have been used to solve GW, and our main idea is to use the following remarkable and non-trivial property: By setting the initial solution to have cyclic symmetry, all intermediate solutions and matrices appearing in the gradient-based algorithms have the same cyclic symmetry until convergence. Based on this property, our gradient-based algorithms restrict the solution space to have cyclic symmetry and update only one of the symmetric parts of solutions and matrices at each iteration, which results in fast computation. Furthermore, the original gradient-based algorithms and ours must solve the Optimal Transport problem (OT) at each iteration, but only in ours does this problem exhibit cyclic symmetry. This cyclic OT can be solved efficiently, and as a result, the total computational time of our algorithms is dramatically faster than the original ones. Experiments showed the effectiveness of our algorithms in synthetic and real-world data with strict and approximate cyclic symmetry, respectively.