Metraipolis › archive › dc_8167228671f7
Partial Optimal Transport on the Circle for All Transported Masses in O(N log N) — arXiv:2608.23910
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.23910
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T06:35:38.877Z
- SHA-256 of the archived text
d197a637f6ba9b9d3dcb956178fe9c829845812fc8748fd2cdf4e7ea268133b4- Stable URL of this page
https://metraipolis.com/documento/dc_8167228671f7
How to cite
Partial Optimal Transport on the Circle for All Transported Masses in O(N log N) — arXiv:2608.23910 — arXiv (en), https://arxiv.org/abs/2608.23910 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8167228671f7 (Metraipolis archive dc_8167228671f7, sha256 d197a637f6ba9b9d3dcb956178fe9c829845812fc8748fd2cdf4e7ea268133b4)
BibTeX
@misc{dc8167228671f7,
title = {Partial Optimal Transport on the Circle for All Transported Masses in O(N log N) — arXiv:2608.23910},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.23910},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8167228671f7; sha256 d197a637f6ba9b9d3dcb956178fe9c829845812fc8748fd2cdf4e7ea268133b4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.23910. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Partial optimal transport compares two measures while leaving part of the mass unmatched, which is what makes it robust to outliers, occlusion, and clutter. The quantity of interest is usually the whole profile - the optimal cost at every transported cardinality - because the right amount to transport is rarely known in advance, and on the real line the PAWL algorithm returns that profile in $O(N\log N)$. Much data is periodic rather than linear: angles, phases, orientations, time of day, hue, and every direction obtained by projecting onto a great circle. On the circle the same problem acquires a global circulation, or equivalently an optimized cut, which the naive exact method handles by running the line algorithm once per support gap, at $O(N^{2}\log N)$. We show that this factor $N$ is unnecessary. The line structure survives in cut-free form, and a free-gap invariant supplies, at every step, a cut at which all previous local updates remain valid line updates. This yields PAWC: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality. Slicing over great circles extends it to $\mathbb{S}^{d-1}$. Empirically the whole profile costs $0.56$ms at $N=4096$ against $1.5$s for a single transported fraction from a general solver; on occluded, cluttered mpeg-7 shapes, holding the descriptor fixed and varying only the cost, it retains $66\%$ of the clean-data retrieval score against $16\%$ for balanced circular OT, and on $\mathbb{S}^{2}$ it halves the fitting error of spherical sliced Wasserstein against contaminated targets, synthetic and real. Code is available at this https URL .
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-26 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.23910 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T06:28:52.199Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-26?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).