Research map / Learning theory and algorithms / Optimal transport
LCOT: Linear Circular Optimal Transport
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.
Introduces Linear Circular Optimal Transport (LCOT), a closed-form linear embedding of circular probability measures via Monge maps from the uniform reference, giving a fast metric approximating circular OT.
Problem
Comparing probability measures on the unit circle with optimal transport is expensive because circular OT generally lacks a closed-form solution and requires optimization over cut points and couplings.
Approach
Linearize circular OT with respect to the uniform reference measure: the closed-form COT Monge map from Unif(S^1) to each target gives an explicit embedding, and the L2 distance between embeddings defines LCOT, which equals COT_2 to the reference and is computable in O(N) per pair.
Key results
- LCOT pairwise distance computation is O(K^2 N + KN) versus O(K^2 N ln(1/eps)) for COT, with timing experiments confirming the speedup for K up to 64 and N up to 20000.
- In MDS experiments on six classes of circular densities, LCOT gives distinct class boundaries, outperforming COT, OT and Euclidean distances visually.
- LCOT barycenter is computed directly as the inverse of the averaged embeddings, recovering the correct barycenter without optimization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the closed-form LCOT embedding with a uniform reference instead of pairwise COT optimization | Pairwise comparison of circular measures · K discrete measures with N points each | time complexity: \mathcal{O}(K^2N\ln(1/\epsilon)) -> \mathcal{O}(K^2N+KN) | Helped |
| Use LCOT rather than COT to represent translated circular densities | Circular density MDS · Translated density families | geometry captured | No clear effect |
| Use LCOT distances rather than COT, OT, or Euclidean distances | MDS of six circular density classes · Six circular density classes | class separability | Helped |
| Compute the barycenter by averaging LCOT embeddings and applying the inverse embedding | LCOT · Circular density barycenter | barycenter recovery | Helped |
Limitations
- Closed-form embedding is exact only for uniform reference measure and quadratic cost; general reference needs binary search.
- LCOT is a linear embedding, not Euclidean, since the circle distance is not a norm-induced inner product.
- Evaluation is limited to synthetic densities and visual MDS assessments rather than downstream task benchmarks.
Experimental setup
Datasets: synthetic von Mises and wrapped skew-normal circular densities
Metrics: wall-clock time MDS embedding separability barycenter recovery
Baselines: Circular optimal transport (COT) Optimal transport with fixed cutting point (OT) Euclidean distance
Builds on: Linear Optimal Transport (LOT) Cumulative distribution transform (CDT) Circular optimal transport (COT)
Closest papers by meaning
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.84)
- An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph (NeurIPS 2025 · similarity 0.84)
- Optimal Transport with Cyclic Symmetry (AAAI 2024 · similarity 0.83)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.83)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.83)
- Linear Partial Gromov-Wasserstein Embedding (ICLR 2025 · similarity 0.83)
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.