Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)

Soheil Kolouri

cs.LGAug 24, 2026

Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)

Authors: Soheil Kolouri

Organizations: College of Connected Computing Vanderbilt University, Nashville, TN

Abstract

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 https://github.com/mint-vu/Partial_Wasserstein_on_Circles.

Figures & tables

Panel of Figure 1 — Figure 1: Partial transport on the circle. (a) solid arcs are geodesic transports between selected atoms; hollow atoms are left unmatched, their mass destroyed at $\partial_{\rm d}$ or created at $\partial_{\rm c}$ . (b) at a fixed transported cardinality $|M|=k$ those two amounts are constants, so any fixed penalties $\lambda_{\rm d},\lambda_{\rm c}$ contribute a constant and the problem is exactly the cardinality-constrained matching ( 2 ).

Panel of Figure 2 — Figure 2: A candidate cell and its exact local cost increment. The inactive endpoints $u$ and $v$ are cyclic neighbours of opposite type and the open interior $\mathcal{C}^{\circ}$ is active and balanced. Before activation the interior atoms are matched in sorted order; activating $u,v$ revokes every match inside the cell (grey dashed) and replaces it by the new sorted matching (magenta), while every match outside the cell is untouched. The increment is therefore $\mathfrak{m}(\mathcal{C})=c_{\mathbb{R}}(\mathcal{C})-c_{\mathbb{R}}(\mathcal{C}^{\circ})$ , computable from the atoms of the cell alone — the circular analogue of PAWL ’s chain update ( Chapel and Tavenard, 2025 ) .

Panel of Figure 3 — Figure 3: Merging two cells after an activation. The new cell inherits a free gap from one of its parents, so Lemma 1 is maintained at $O(1)$ cost, and that gap is a cut at which every update made so far is a valid line update.

Panel of Figure 4 — Figure 4: Spherical slicing, after Bonet et al. (2023, Figure 1) . (a) atoms of $\mu$ (blue) and $\nu$ (orange) on $\mathbb{S}^{d-1}$ , the great circle $\mathcal{C}_{U}$ (dashed behind the sphere), and the geodesic projection of each onto it. (b) the circular problem that slice induces, with a cardinality- $3$ matching and a free gap $\theta^{\star}$ . PAWC returns the optimal matching for every $k$ in one $O(N\log N)$ sweep per slice.

Panel of Figure 5 — Figure 5: Measured cost of the complete profile. Baseline B is the cut-envelope solver, Baseline A the LP oracle; dashed segments are extrapolated ( $N^{2}\log N$ , $N^{3}$ ). Fitted log–log slopes: $1.03$ – $1.29$ for PAWC against $2.00$ for B.

Panel of Figure 6 — Figure 6: Partial matching of shape descriptors on mpeg-7 . (a) one query: the visible arc of the boundary (green), the occluded remainder (grey), and the normal-angle measure the matcher sees, with clutter in red. (b) orientation success against clutter at half the boundary visible and (c) retrieval bullseye against the visible fraction at $20\%$ clutter, for PAWC at a fixed $\rho=0.8$ , full circular OT, and the extended-Gaussian-image correlation matcher. OT fails on clutter; correlation fails on occlusion.

		orientation ( $<5^{\circ}$ )			retrieval (bullseye)			correspondence ( $F_{1}$ )
$v$	$c$	PAWC	full OT	corr.	PAWC	full OT	corr.	PAWC	full OT	NN
$1.00$	$0.0$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{0.457}$	$\mathbf{0.457}$	$0.384$	$\mathbf{1.00}$	$\mathbf{1.00}$	$0.77$
$1.00$	$0.2$	$\mathbf{1.00}$	$0.62$	$0.98$	$\mathbf{0.302}$	$0.071$	$0.198$	$\mathbf{0.84}$	$0.21$	$0.69$
$1.00$	$0.4$	$\mathbf{1.00}$	$0.45$	$0.92$	$\mathbf{0.118}$	$0.038$	$0.077$	$\mathbf{0.66}$	$0.12$	$0.53$
$0.70$	$0.0$	$\mathbf{1.00}$	$\mathbf{1.00}$	$0.96$	$\mathbf{0.337}$	$\mathbf{0.337}$	$0.126$	$\mathbf{0.94}$	$\mathbf{0.94}$	$0.77$
$0.70$	$0.2$	$\mathbf{1.00}$	$0.83$	$0.90$	$\mathbf{0.201}$	$0.106$	$0.066$	$\mathbf{0.81}$	$0.45$	$0.69$

Table 1: Shape matching under occlusion and clutter on all

1400

mpeg-7 silhouettes:

v

is the visible fraction of the boundary,

c

the clutter fraction. PAWC transports

\rho=1-c

, so the

c=0

rows are full circular OT and tie by construction. Orientation and correspondence average

212

shapes per cell, retrieval

138

queries against the full database. “corr.” is the correlation matcher at its best of three bandwidths; “NN” is mutual nearest neighbours in normal angle.

Figure 7: Fitting

500

particles to the usgs earthquake catalogue whose minibatches are contaminated at

\varepsilon=0.3

, over a Natural Earth coastline. The blue background is a kernel estimate of the catalogue’s own density — the target the particles should cover. ssw (

\gamma=1

) scatters particles across the Pacific and the continental interiors, where no earthquakes are; the partial fit stays on the ridges and subduction zones.

	synthetic vMF mixture					earthquake catalogue
$\varepsilon$	ssw	sspw	gain	wins	best	ssw	sspw	gain	wins	best
$0.0$	$0.50$	$\mathbf{0.50}$	$0\%$	$0/8$	$14\%$	$0.79$	$\mathbf{0.79}$	$0\%$	$0/8$	$0\%$
$0.1$	$1.97$	$\mathbf{0.79}$	$60\%$	$8/8$	$70\%$	$3.23$	$\mathbf{1.15}$	$64\%$	$8/8$	$77\%$
$0.2$	$7.13$	$\mathbf{2.30}$	$68\%$	$8/8$	$68\%$	$10.25$	$\mathbf{3.05}$	$70\%$	$8/8$	$70\%$
$0.3$	$15.92$	$\mathbf{6.09}$	$62\%$	$8/8$	$63\%$	$21.86$	$\mathbf{10.35}$	$53\%$	$8/8$	$53\%$
$0.4$	$26.40$	$\mathbf{14.46}$	$45\%$	$8/8$	$50\%$	$36.40$	$\mathbf{31.42}$	$14\%$	$7/8$	$40\%$

Table 2: Spherical fitting against a contaminated target, eight seeds per cell. Energy distance to clean target samples,

\times 10^{-3}

. sspw transports the rule fraction

\gamma=1/(1-\varepsilon)

rounded to the grid, so the

\varepsilon=0

row is ssw ; “gain” is the reduction from ssw , “wins” counts seeds ahead, and “best” is the gain at the best

\gamma

of six on the grid, which at

\varepsilon=0

is a selection over noise.

Panel of Figure 8 — Figure 8: Energy distance against $\gamma$ on the synthetic mixture, each curve divided by its own $\gamma=1$ value. The optimum moves right as contamination grows; the clean curve leaves the panel at once.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 9 — Figure 9: Nested optimal active sets (Theorem 6 ). (a) An optimal cardinality- $k$ matching $M_{k}$ on the circle, with matched pairs $(x_{2},y_{1})$ and $(x_{3},y_{2})$ transported along geodesic arcs; solid atoms form the active set $A(M_{k})$ and hollow atoms are inactive. (b) An optimal cardinality- $(k{+}1)$ matching obtained by augmenting along a minimum-cost alternating path: exactly one source atom $x=x_{1}$ and one target atom $y=y_{3}$ are activated (circled), and they are cyclic neighbors among the inactive atoms since every atom between them is already active. The augmentation revokes the edges $(x_{2},y_{1})$ and $(x_{3},y_{2})$ of $M_{k}$ (dashed) and rematches the previously active atoms as $(x_{1},y_{1})$ , $(x_{2},y_{2})$ , $(x_{3},y_{3})$ , so that $A(M_{k+1})=A(M_{k})\cup\{x,y\}$ while $M_{k}\not\subset M_{k+1}$ (Remark 2 ).

Panel of Figure 10 — Figure 10: Common optimal cut (Lemma 3 ). (a) A balanced active set $A=\{x_{2},y_{1},x_{3},y_{2}\}$ and its extension $A^{\prime}=A\cup\{x,y\}$ on the circle. The arc $I$ , oriented from $x$ to $y$ , supports the one-interval update $H_{A^{\prime}}=H_{A}+\mathbf{1}_{I}$ . The support gap $G$ carries zero flow in an optimal circular $W_{1}$ solution for both $A$ (solid arcs) and $A^{\prime}$ (dashed arcs), so cutting in $G$ realizes both circular costs as line costs. (b) The cumulative imbalances, unrolled at a point of the large support gap. $H_{A}$ is flat at its median $a$ on $E=\{H_{A}=a\}$ , while $H_{A^{\prime}}=H_{A}+\mathbf{1}_{I}$ is flat at its median $a{+}1$ on $E\cap I$ ; the gap $G\subset E\cap I$ is at median level for both, hence flow-free for both.

Panel of Figure 11 — Figure 11: Constructive simultaneous cut. The free gap $\theta^{\star}$ is contained in no selected cell, so the complete nested sequence can be cut and unwrapped at the same location. On the resulting line, the active sets grow by local sorted-matching updates and $C_{k,\theta^{\star}}^{\mathrm{line}}=C_{k}^{\circ}$ for every transported cardinality $k$ .

Panel of Figure 12 — Figure 12: Constant-time cell-cost preprocessing on the doubled cyclic sequence. A balanced interval decomposes uniquely into adjacent minimal balanced chains, analogous to the chain decomposition in PAWL ( Chapel and Tavenard, 2025 ) . Repeated differential-rank values identify the minimal chains; their costs are signed-coordinate prefix differences. The accumulated values $Q_{t}$ then provide both the cell cost and its interior cost with constant-time table lookups.

$N$	PAWC (array)	PAWC (compiled)	Baseline B	Baseline A
$10^{2}$	$0.000094$ s	$0.000042$ s	$0.0042$ s	$0.212$ s
$3\cdot 10^{2}$	$0.000177$ s	$0.000052$ s	$0.0315$ s	$4.52$ s
$10^{3}$	$0.000555$ s	$0.000134$ s	$0.349$ s	$226$ s
$3\cdot 10^{3}$	$0.00170$ s	$0.00048$ s	$3.35$ s	—
$10^{4}$	$0.00643$ s	$0.00178$ s	$38.5$ s	$2.26\cdot 10^{5}$ s ‡
$3\cdot 10^{4}$	$0.0217$ s	$0.00574$ s	$357$ s	$6.10\cdot 10^{6}$ s ‡

Appendix

Table 3: Time to compute the complete partial-transport profile for all

k

, mean of five repetitions (two for Baseline A at

N\geq 600

). † extrapolated along

N^{2}\log N

, ‡ along

N^{3}

, in both cases with the constant fitted at the largest measured size; a dash marks sizes past which no extrapolation is attempted. At

N=10^{6}

the compiled implementation returns every cardinality in

0.365

s, against roughly six days for cut enumeration. Baseline A already needs almost four minutes at

N=10^{3}

, where PAWC needs

1.3\cdot 10^{-4}

cut rule	instances failing	median	90th pct	worst
$\min\Theta_{K}$ (optimal at $k=K$ )	$13.5\%$	$0.09$	$1.0$	$1.8\cdot 10^{3}$
widest support gap	$22.6\%$	$0.21$	$0.7$	$2.2$
warm start at $k_{0}=K/2$	$38.9\%$	$0.28$	$28$	$3.4\cdot 10^{4}$
uniformly random gap	$100\%$	$0.26$	$60$	$8.3\cdot 10^{3}$

Appendix

Table 4: One-cut rules against the exact envelope,

5600

exact instances. A rule fails on an instance when its cut is strictly suboptimal at some

k

; the excess columns are

\max_{k}\varepsilon_{k}

over the instances where it does, with

\varepsilon_{k}=(C_{k,r}^{\mathrm{line}}-C_{k}^{\circ})/C_{k}^{\circ}

. Every cut is a valid upper bound ( Corollary 2 ); only looseness is at issue.

Panel of Figure 13 — Figure 13: (a) Failure rate of the deterministic rule $\min\Theta_{K}$ by instance family, $800$ instances each. (b) The family of Example 1 : measured relative excess at $k=1$ of a cut that is exactly optimal at $k=K$ , against the closed form ( 28 ), in exact arithmetic over six decades of $\delta$ .

	what it isolates	vs. POT	vs. LP oracle
(a)	circular solver alone, no projection	$3.3\cdot 10^{-15}$	$1.4\cdot 10^{-15}$
(b)	per slice on the sphere, $384$ slices	$7.5\cdot 10^{-9}$	$5.6\cdot 10^{-15}$
(c)	the aggregate ( 49 ) against $\mathrm{SSW}_{1}$	$1.3\cdot 10^{-9}$	–
(d)	the mass factor ( 50 ), four $(n,w)$	$1.5\cdot 10^{-15}$	–
(e)	the $d=2$ degeneracy of Remark 5	$7.9\cdot 10^{-16}$	–

Appendix

Table 5: Maximum relative discrepancy of the reduction cross-check, over

d\in\{3,5,10,50\}

n=m\in\{10,50,200\}

and both instance families, with slices shared between implementations. Check (e) additionally has zero slice-to-slice variance (

6.7\cdot 10^{-16}

), as it must, since at

d=2

the projection is an isometry and every slice returns the same value.

Panel of Figure 14 — Figure 14: (a) The effective Hoeffding range $\max_{\ell}Z_{\ell}-\min_{\ell}Z_{\ell}$ as a fraction of the ceiling $\pi s$ used in Proposition 4 , against transported cardinality; median over families, $M_{\mathrm{ref}}=10^{5}$ . The ceiling is never approached, and the gap widens as $s$ shrinks. (b) The ratio of the per-breakpoint term of the uniform bound ( 54 ), which uses the range $\pi Kw$ , to the pointwise bound ( 53 ) at the same $s$ , which uses $\pi s$ ; $\varepsilon=0.05\,Kw$ , $M=2^{12}$ . The two coincide at $s=Kw$ and diverge without limit as $s\to 0$ .

Explore similar work

May 19, 2026

Take It or Leave It: Intent-Controlled Partial Optimal Transport

While optimal transport (OT) enforces a rigid constraint by requiring two measures to be matched exactly, partial optimal transport relaxes this requirement by allowing mass to remain unmatched through a global budget, scalar rebate, or uniform rejection rule. However, many applications call for more structured, pointwise rejection mechanisms, where the decision to leave mass unmatched depends on side-specific reliability, support geometry, or external information about which components should participate in the comparison. We introduce intent-controlled partial optimal transport (IC-POT), a targeted generalization of partial transport that replaces the global rejection paradigm with pointwise rejection costs over both measures. We show that the resulting optimization problem admits a dual interpretation in terms of local acceptance thresholds and can be solved by recasting it as a balanced Kantorovich OT problem on an augmented support. Beyond theoretical analysis, we demonstrate the practical relevance of IC-POT in settings where rejection is driven by side information. In positive-unlabeled learning and open-partial domain adaptation, incorporating pointwise rejection rules that encode statistical structure improves fixed baseline pipelines. Finally, we motivate the use of IC-POT with a geophysical practical case: multi-modal satellite ocean measurements, for which physical and sensors priors naturally inform the rejection mechanism and define the retrieved comparable signal information.

Salil Parth Tripathi, Bertrand Chapron, Fabrice Collard +2

OceanDataLab · Ifremer · Université Bretagne Sud +1

Inverse Optimal Transport Optimal Transport

Ask PDF

Apr 27, 2026

Sliced-Regularized Optimal Transport

We propose a new regularized optimal transport (OT) formulation, termed sliced-regularized optimal transport (SROT). Unlike entropic OT (EOT), which regularizes the transport plan toward an independent coupling, SROT regularizes it toward a smoothened sliced OT (SOT) plan. To the best of our knowledge, SROT is the first approach to leverage a version of SOT plan as a reference to improve classical OT. We provide a formal definition of SROT, derive its dual formulation, and provide a post-Bayesian interpretation of SROT. We then develop a Sinkhorn-style algorithm for efficient computation, retaining the same scalability advantages as EOT. By incorporating a scalable SOT plan as a prior, SROT yields more accurate approximations of the exact OT plan than EOT under the same level of regularization. Moreover, the resulting transport plan improves upon the reference SOT plan itself. We further introduce the corresponding OT divergence induced by SROT, named SROT divergence, and analyze its topological and computational properties. Finally, we validate our approach through experiments on synthetic datasets and color transfer tasks, demonstrating that SROT is better than both EOT and SOT in approximating exact OT. Additional experiments on gradient flows further highlight the advantages of SROT divergence.

Khai Nguyen

The University of Texas at Austin

Optimal Transport

Ask PDF

Apr 16, 2026

Amortized Optimal Transport from Sliced Potentials

We propose a novel amortized optimization method for predicting optimal transport (OT) plans across multiple pairs of measures by leveraging Kantorovich potentials derived from sliced OT. We introduce two amortization strategies: regression-based amortization (RA-OT) and objective-based amortization (OA-OT). In RA-OT, we formulate a functional regression model that treats Kantorovich potentials from the original OT problem as responses and those obtained from sliced OT as predictors, and estimate these models via least-squares methods. In OA-OT, we estimate the parameters of the functional model by optimizing the Kantorovich dual objective. In both approaches, the predicted OT plan is subsequently recovered from the estimated potentials. As amortized OT methods, both RA-OT and OA-OT enable efficient solutions to repeated OT problems across different measure pairs by reusing information learned from prior instances to rapidly approximate new solutions. Moreover, by exploiting the structure provided by sliced OT, the proposed models are more parsimonious, independent of specific structures of the measures, such as the number of atoms in the discrete case, while achieving high accuracy. We demonstrate the effectiveness of our approaches on tasks including MNIST digit transport, color transfer, supply-demand transportation on spherical data, and mini-batch OT conditional flow matching.

Minh-Phuc Truong, Khai Nguyen

Hanoi University of Science and Technology · The University of Texas at Austin

Optimal Transport

Ask PDF