Research map / Learning theory and algorithms / Optimal transport
Optimal Transport with Cyclic Symmetry
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes cyclic-symmetry-aware algorithms that reduce cyclic optimal transport (LOT, strongly convex/entropic OT) to much smaller problems, including a cyclic Sinkhorn and a two-stage Sinkhorn for approximate symmetry.
Problem
Solving discrete optimal transport is expensive when inputs have n-order cyclic symmetry (block-circulant cost, periodic marginals); standard solvers ignore this structure and work with d^2 variables.
Approach
Exploit block-circulant structure: the cyclic LOT reduces exactly to a small m×m LOT with cost G_ij = min_k C_ijk and recovers the full plan analytically; for SROT/EROT the Fenchel dual has only 2m variables, giving a cyclic Sinkhorn with a modified Gibbs kernel K_ij = sum_k exp(-C_ijk/λ) and O(m^2) per iteration; a two-stage Sinkhorn handles approximate symmetry.
Key results
- On synthetic data with d=10000 and n=50, cyclic network simplex took 0.329 s versus 33.66 s for network simplex, with identical objective values (6.526).
- On synthetic d=10000 with n=50, cyclic Sinkhorn took 0.320 s versus 14.589 s for Sinkhorn with identical objective values.
- On 64x64 real images, two-stage Sinkhorn matched Sinkhorn's objective (4.320) and zero marginal error while reducing time from 16.61 s to 13.88 s; plain cyclic Sinkhorn was faster (3.84 s) but had 0.001 marginal error and a different objective.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cyclic network simplex with n = 50 instead of network simplex | LOT on synthetic data · d = 5000 and d = 10000 | Time (sec.): 6.523 ± 1.013 -> 0.056 ± 0.015; 33.660 ± 3.238 -> 0.329 ± 0.034 | Helped |
| Use cyclic Sinkhorn with n = 50 instead of Sinkhorn | EROT on synthetic data · d = 5000 and d = 10000 | Time (sec.): 3.271 ± 1.445 -> 0.067 ± 0.034; 14.589 ± 4.213 -> 0.320 ± 0.053 | Helped |
| Use cyclic Sinkhorn with n = 50 instead of Sinkhorn | EROT on synthetic data · d = 5000 and d = 10000 | Obj. value: 6.233 ± 0.821 -> 6.233 ± 0.821; 6.745 ± 0.916 -> 6.745 ± 0.916 | No clear effect |
| Use cyclic Sinkhorn instead of Sinkhorn | EROT on approximately symmetric NYU images · 64×64 and 96×96 | Time (sec.): 16.610 ± 6.502 -> 3.837 ± 1.286; 117.152 ± 53.442 -> 26.087 ± 11.985 | Helped |
| Use cyclic Sinkhorn instead of Sinkhorn | EROT on approximately symmetric NYU images · 64×64 and 96×96 | Obj. value: 4.320 ± 2.056 -> 4.289 ± 2.048; 6.296 ± 3.100 -> 6.250 ± 3.089 | Mixed |
| Add a cyclic Sinkhorn initialization stage before original Sinkhorn | EROT on approximately symmetric NYU images · 64×64 and 96×96 | Time (sec.): 16.610 ± 6.502 -> 13.877 ± 6.244; 117.152 ± 53.442 -> 91.790 ± 43.000 | Helped |
| Add a cyclic Sinkhorn initialization stage before original Sinkhorn | EROT on approximately symmetric NYU images · 64×64 and 96×96 | Obj. value: 4.320 ± 2.056 -> 4.320 ± 2.056; 6.296 ± 3.100 -> 6.296 ± 3.100 | No clear effect |
Surprising findings
- The naive approach of solving OT on only one symmetric component and replicating the solution fails, because interactions between symmetric components matter (shown by counter-example).
Limitations
- The cyclic order n must be known in advance.
- Theoretical analysis of the two-stage Sinkhorn on approximately symmetric inputs is left for future work.
- Experiments are limited to synthetic data and mirror-symmetric (n=2) real images; the approach is not shown for other symmetries such as dihedral.
Experimental setup
Datasets: NYU Symmetry Database synthetic random block-circulant data
Benchmarks: synthetic block-circulant OT (d=5000, 10000) NYU Symmetry Database image pairs (64x64, 96x96)
Metrics: objective value marginal error computation time (s)
Baselines: Network Simplex Sinkhorn
Builds on: Sinkhorn algorithm network simplex algorithm entropy-regularized optimal transport Fenchel duality
Closest papers by meaning
- Submodular framework for structured-sparse optimal transport (ICML 2024 · similarity 0.86)
- Gromov-Wasserstein Problem with Cyclic Symmetry (CVPR 2025 · similarity 0.85)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.85)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.85)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.85)
- An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.