acceptodds
Under review as a conference paper at ICLR 2027

Circular Optimal Partial Transport

Abstract

When two signals share only part of their content, optimal partial transport (OPT) can match that common content without assigning every observation a counterpart. For periodic signals, the samples lie on a circle, and their cyclic ordering requires more than a direct use of a line solver. PAWC computes the complete circular partial-transport profile for the cost on distinct support. Building on the PAWL and PAWC profile algorithms, we introduce COPT, an exact solver for circular OPT between empirical measures with a penalty on unmatched mass, an arbitrary convex radial cost, and possibly repeated support points. We extend PAWC's local augmentation and simultaneous-cut arguments to convex costs, using a rank refinement to handle repeated support and flat cost regions. We prove that COPT returns the complete profile of optimal costs over all transported cardinalities in time and memory, where is the number of atoms and the largest transported cardinality, and in time for integer power costs. We further extend COPT to spherical measures through great-circle slicing and to repeated comparisons through a linear embedding, and we establish their metric properties. Through numerical experiments on correspondence recovery, partial shape matching, foreground retrieval, and directional data, we demonstrate the computational benefits of COPT and its robustness to missing signal and background clutter.

Primary area:
optimization
Keywords:
optimal transport, partial optimal transport, circular optimal transport, computational optimal transport, unbalanced optimal transport, circular data

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_JaJbOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces a solver for partial optimal transport on the circle when the ground cost is a convex function of the radial cost. The authors show that the problem can be solved with an adaptation of PAWC algorithm that provides local augmentation . They also show that the problem can be solved and return all optimal solutions for all cardinality in O(n log n+ k^2) where k is the largest cardinality of the support of the optimal plan. Numerical experiments illustrate the proposed algorithm on a toy example, partial alignment and foreground palette retrieval. The authors also propose extension of the method for slices partial OT on the sphere and linear version of the problem.

Critical strengths
  • Extension of the PAWC, algorithm to solve partial OT on the circle for more general costs is interesting and makes nice connections between the recent work of Kolouri 2026 and of Angrick 2026.
Critical weaknesses
  • The paper is not very well written and the presentation is not always clear or even self content for instance many subtleties of PAWC are not explained. The numerical experiments are not detailed enough in the main paper and require to read the supplementary material to understand the results. This means that the main paper is not self contained and the reader has to read the supplementary material to understand the results, which is a way to cheat with the page limit.

  • The paper is an extension of PAWC (Kolouri 2026) that is itself a non published extension of the PAWL (Chapel 2025). It seems that it merges the proof tools from (Kolouri 2026) and the extension of OT on the line to more general costs of (Angrick 2026). In this sens it makes an interesting connexion but it is quite incremental and the novelty is limited.

  • The numerical experiments are not very convincing, they do not really show why more general costs are necessary and are done on simulated partial OT problems or on problems that are quite far from real applications. Most of them are also not detailed and provided only in the supplementary material.

  • Spherical Sliced COPT and Linear COPT are introduced, discussed and their numerical experiments are hinted at all in one paragraph in the main paper and are not detailed enough to be convincing. This makes the paper feel like a collection of ideas/flag planting rather than a coherent story.

Questions for authors
  • What was the motivation for studying more general costs? Are there any real applications where this is necessary? It is more and more important that research focus on understanding and intuition to guide applications and this is missing in the submission. This is also related to my comment above about experiments where no understanding or intuition is given about when this would be useful.

  • What is the novelty in the proof that goes beyond merging (Kolouri 2026) and (Angrick 2026)?

  • Minor comment. SInce the paper is strongly related to partial OT on the line (and circle) some references might be interesting to discuss. In particular [A] below that discuss squared distance on the line.

[A] Bonneel, N., & Coeurjolly, D. (2019). Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38(4), 1-13.

5 comments
AuthorsOpenReview ↗

Response to JaJb (part 1)

We appreciate your close reading and insightful questions about the method's motivation and practical use.

The main text should explain the method and experiments without relying on the appendix.

We agree that the submitted main text needed a fuller explanation of why the cell updates suffice and how the experiments were evaluated, and we now explain the update by asking what must change when one more pair is transported. In Section 4's worked example, keeping the first pair and appending the second increases the cost by 1/41/4, while allowing the partners within the cell to change costs only 7/1007/100. This calculation motivates the search over cell updates; the locality lemma then proves that one of those updates reaches the next global optimum. We complete the explanation by deriving the common cut at which sorting recovers a plan for any recorded cardinality.

We also expanded Section 5 so that the reported scores can be read in terms of their tasks. For MPEG-7, we measure normalized symmetric RMS contour error after rotation recovery and class Recall@40 for retrieval. For Flowers, we retrieve an image's clean foreground palette from a query containing real background pixels. The main text now includes the sampling, corruption and class-disjoint validation procedures for these studies, while the fixed-mass fitting comparison below tests the cost choice beyond partial transport itself.

The motivation and practical need for costs beyond W1W_1 are unclear.

We agree that a larger cost class needs an application-level motivation, and our aim is to preserve the chosen displacement loss when only part of each measure is transported. Rabin, Delon and Gousseau develop this motivation for circular OT by studying powers and Huber costs under position and weight perturbations [1]. The choice can change which circular plan is preferred even when transported mass is fixed, so retuning λ\lambda cannot reproduce it, since the penalty λ(N−2k)\lambda(N-2k) is constant across plans of cardinality kk.

For instance, preserving the quadratic reference geometry of LCOT and LOPT [2,3] requires squared-distance optima in a partial circular counterpart. Squared cost can also be chosen from a residual model, since minimizing it maximizes conditional association likelihood under independent circular geodesic-normal errors of common concentration, uniform clutter and a prescribed cardinality [5]. Nonlinear angular costs are also used in applied evaluation, as in LOCATA's source-tracking scores at OSPA orders 1 and 5 [6]. These precedents motivate a solver that accepts the chosen cost without restricting the application to W1W_1.

We tested the practical benefit on the USGS task from the submission, using real catalogue observations with generated contamination following PAWC's design [4]. With 500 particles and 32 shared slices, both costs retain 500 of 625 targets, so neither can improve merely by discarding more mass. Using each cost for both transport and updates, quadratic fitting lowers mean held-out chordal energy by 18.9% over 20--40% uniform contamination after 8,000 updates. Holding each update rule fixed in turn, quadratic-optimal plans lower mean error over these levels by 22.2% under W1W_1 updates and 24.3% under quadratic updates, improving all sixteen seeds at each level. This supports the benefit of the transport plans themselves. Quadratic plans with W1W_1 updates have the lowest five-level mean, while ordinary W1W_1 fitting is better on clean data and at 10% contamination (Table 1 and Appendix K.10, including paired intervals).

Equal update counts allow the more expensive cost more computation, so we also tested both costs with 180 seconds of warmed USGS fitting through COPT. Quadratic fitting still lowers mean error over 20--40% uniform contamination by 18.5%, improving all eight new seeds at each level despite completing about 9% fewer updates. Appendix K.10 reports every level, including the clean and 10% conditions favoring W1W_1.

Because the preferred cost varies with the setting, we evaluated choosing it on validation data in a further USGS study. One Huber configuration selected across all five uniform-contamination levels lowers mean test energy over those levels by 14.6% against W1W_1 with its own validation-selected rate, holding the quota fixed across costs, in sixteen further seeds.

AuthorsOpenReview ↗

Response to JaJb (part 2)

What does the proof add beyond PAWC and Angrick et al.?

We appreciate your careful comparison with PAWL/PAWC [4,8] and Angrick et al. [7], whose ideas are important foundations of our method. Building on those works, we establish globally optimal profile growth and common-cut recovery for convex costs and ties. To apply Angrick et al.'s line argument, we would first need a cut valid for the nonlinear objective. PAWC's intermediate common-cut statement for arbitrary nested balanced sets cannot establish that cut for squared cost (Appendix C.1). Appendix C.2 constructs distinct balanced supports with a unique W1W_1 optimum for which every W1W_1-optimal cut has full-cardinality quadratic line cost approaching kk times the circular optimum, where kk is the number of atoms per measure. Thus reusing a W1W_1-optimal cut has no cardinality-independent constant-factor guarantee.

We therefore adapt the endpoint argument directly to circular arcs and prove locality before choosing the cut. If a minimum-net-cost augmentation from a refined optimum crossed a previously inactive path endpoint, we could remove a non-improving equal-cardinality exchange while shortening the refined arc. We use rank length to keep this shortening strict under coincident support and flat costs. One optimal augmentation must then stay in a cell, where Monge sorting attains its cost, and PAWC's free-gap induction can recover a common ordinary or virtual cut for the history. For tied inputs, virtual cuts recover optima missed by ordinary cuts; Angrick et al.'s interval tools accelerate integer powers.

The submitted Appendices A.3--A.4 already contain the locality and common-cut proofs. To check their consequences in the implementation, we compared every profile value, recovered plan and common-cut lift with an integer-cost oracle on 170,900 profiles, including cases requiring virtual cuts (Appendix B).

The spherical and linear extensions need fuller development and evaluation.

Thank you for asking us to explain more clearly why these sections belong in the paper. The circular solver is our main contribution, and the extensions develop two uses of its costs and plans. Great-circle methods compare spherical data through circular projections, while reference methods reuse transport plans across many comparisons, as in LCOT, LOPT and LSSOT [2,3,9]. We build on these established constructions to study how they handle incomplete observations. Presenting this development with the solver allows the paper to follow circular OPT from its computation to its use as a distance and a reusable representation.

Their brief treatment in the submitted main text obscured the work supporting them. These are not proposals whose proofs or evaluation are deferred to future papers. Partial transport raises a substantive question in each construction, because the mass omitted from a plan still affects the comparison or representation.

For spherical data, we prove that the rooted penalized integral for power costs is a metric on finite positive measures, with finite-slice estimates forming pseudometrics. The retrieval experiments evaluate this distance, while the fitting study examines the nonlinear circular plans during optimization. That study also answers the question about the broader cost class. At fixed transported mass, quadratic fitting reduces mean held-out error by 18.9% over 20--40% uniform contamination, and the four-arm comparison tests the contribution of the transport plan under either update rule (Table 1).

For reference representations, we must determine what to do with target observations omitted by the partial plan. Retaining their locations allows reconstruction of each unit-atom circular target and supports a reference metric that agrees with the OPT metric against the reference. Compressing them to their total mass reduces computation but loses metricity. We evaluate this choice on 320 ModelNet measures with 48 atoms and eight slices, including encoding and all pairwise comparisons after shared projection, using assignment for direct and residual transport costs.

RepresentationAll-pairs time (s)SpeedupSpearman
Pairwise COPT13.6931.00×1.00\times1.000
Full reference representation8.8941.54×1.54\times0.979
Compressed representation0.93914.58×14.58\times0.967

The retrieval study then tests the practical consequence of retaining those locations. With 24 slices, the full representation achieves 27.5% acc, compared with 28.4% for direct COPT and 19.4% after compression. The reference representation can be constructed on each circular projection, so the two extensions also combine in comparisons of spherical data.

AuthorsOpenReview ↗

Response to JaJb (part 3)

(continued from Part 2 - The spherical and linear extensions need fuller development and evaluation)

We therefore include them as developed consequences of the circular OPT formulation, with their own guarantees and measured benefits, while keeping the circular optimality and complexity results as the paper's main contribution. Sec 6 now presents enough of that development in the main text to assess both the connection and the results.

Please discuss reference [A] on squared-distance transport on the line.

Thank you for adding the reference. SPOT [10] develops a fast quadratic-cost solver on the line and uses it in sliced transport for color transfer and registration. It transports every point of the smaller set to a subset of the larger set, fixing the mass at the smaller cardinality. In the penalized OPT formulation [11], either measure may contain observations with no counterpart; COPT computes the corresponding circular optima at every cardinality. The additional ordering problem is why we establish circular locality and common-cut recovery. Related Work now describes SPOT's line solver and its use through slicing.


Once again we thank the reviewer for the insightful critique. We would be happy to discuss further to address any other concerns you may have, or clarify existing comments as well.

Best regards, authors

[1] Rabin, Delon and Gousseau, Transportation Distances on the Circle, JMIV 2011, Sections 3.1--3.3.

[2] Diaz Martin et al., LCOT, ICLR 2024, Definition 3.1 and Remark 3.3.

[3] Bai et al., Linear Optimal Partial Transport Embedding (LOPT), ICML 2023.

[4] Kolouri, PAWC, arXiv 2026, Section 6.3 and Appendix L.3.

[5] Coeurjolly and Le Bihan, Geodesic Normal Distribution on the Circle, Metrika 2012. The likelihood interpretation above is conditional, not an assumption about USGS.

[6] Evers et al., The LOCATA Challenge, IEEE/ACM TASLP 2020, Section VII.B.3 and Table V.

[7] Angrick et al., Computing All Optimal Partial p-Wasserstein Matchings on the Line, arXiv 2026.

[8] Chapel and Tavenard, PAWL, ICLR 2025.

[9] Liu et al., Linear Spherical Sliced Optimal Transport (LSSOT), ICLR 2025.

[10] Bonneel and Coeurjolly, SPOT, ACM TOG 2019.

[11] Bai et al., Sliced Optimal Partial Transport (SOPT), CVPR 2023.

Reviewer_nGLFOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces an exact solver for partial optimal transport between empirical measures with a penalty on unmatched mass, an arbitrary convex radial cost, and possibly repeated support points. The paper extends previously introduced partial optimal transport profiling methods to arbitrary convex costs and further extends developed methodology to spherical measures. The paper demonstrates the utility of developed methodology through numerical experiments on correspondence recovery, partial shape matching, foreground retrieval, and directional data.

Critical strengths
  1. The paper deals with the partial optimal transport on circle, which can have applications in both machine learning and signal processing.
  2. Methodology developed in paper has clear theoretical guarantees.
  3. Proposed Methodology in paper has been tested on variety of tasks.
Critical weaknesses

Weakness in proposed methodology Proposed methodology and profiling approach is only useful in the case of uninform weights, whereas many practical problems involve non-uniform weights. Authors should give a brief sketch of how the methodology developed in paper extends to non-uniform masses.

Weakness in presentation

  1. While overall presentation and quality of paper is good, section 4 of the paper needs improvements. It should be rewritten such that it is self-contained and provide the necessary intuition to the reader on to why algorithm is true.
Questions for authors

Authors should focus on above mentioned weaknesses.

2 comments
AuthorsOpenReview ↗

Response to nGLF (part 1)

Thank you for your encouraging assessment and valuable suggestions on the weighted extension and method presentation. Section 4 now explains the cell update and the weighted reduction below.

How does the method extend to nonuniform masses?

You are right that nonuniform masses are important in applications, so we have added a reduction that represents weights with a common mass quantum by coincident copies, allowing one location to send mass to several targets.

If ai=qria_i=q r_i and bj=qsjb_j=q s_j, with q>0q>0 and nonnegative integer counts, we replace each location by rir_i or sjs_j copies and compute their profile Ck∘C_k^\circ. For Nq=∑iri+∑jsjN_q=\sum_i r_i+\sum_j s_j, the original penalized value is

qmin⁡k{Ck∘+λ(Nq−2k)}.q\min_k\{C_k^\circ+\lambda(N_q-2k)\}.

Flow integrality proves that multiplying values and flows by qq, without rescaling λ\lambda in the copy problem, recovers the weighted optimum, with the copy assignments aggregated to permit split flows between the original locations. At fixed mass we obtain V(qk)=qCk∘V(qk)=qC_k^\circ, with linear interpolation between successive grid masses, which also determines the optimum at masses that are not integer multiples of qq.

To illustrate how a split is recovered, consider source locations (0,1/2)(0,1/2) with masses (1/2,1/4)(1/2,1/4) and target locations (1/8,3/8)(1/8,3/8) with masses (1/4,1/2)(1/4,1/2). With squared cost and q=1/4q=1/4, the copy profile yields the following weighted costs.

kkMass qkqkTransport cost qCk∘qC_k^\circλ=0.03\lambda=0.03λ=0.1\lambda=0.1
0000.0450.15
11/41/41/2561/2560.033906250.10390625
21/21/21/1281/1280.02281250.0578125
33/43/411/25611/2560.042968750.04296875

At full mass, the first source sends 1/41/4 to each target; the copies recover the split without requiring a one-to-one map between the original weighted locations.

We also checked the construction on our chroma inputs, whose twelve bins have unequal counts totaling 72 atoms. On eight predetermined real pairs, the values agree with compact LPs at every tested grid and half-grid mass and penalty, including a 5/725/72 source mass split into 4/724/72 and 1/721/72 (Appendix A.6).

For arbitrary weights, we round down to multiples of qq without renormalization and bound the effect of the discarded mass Δ\Delta. The optimum changes by at most λΔ\lambda\Delta, while the recovered plan remains feasible for the original measures within 2λΔ2\lambda\Delta of optimum. Appendix A.6 proves these bounds and specifies a quantum for any prescribed absolute accuracy. Computation is measured in the number of copies NqN_q; avoiding that expansion would require updates that track residual capacities directly.

AuthorsOpenReview ↗

Response to nGLF (part 2)

Section 4 should be self-contained and explain why the algorithm works.

We agree that Section 4 should explain why a local update reaches a global optimum without relying on familiarity with PAWC, and have reorganized the section around that argument. A cell lies between consecutive inactive atoms and contains equally many active sources and targets; we add opposite-type endpoints and sort the enlarged active sets, allowing the old partners to change. Monge uncrossing proves that this is the best plan within the enlarged cell, whose cost minus the previous interior cost defines the candidate increment. What remains to prove is that considering these candidates does not omit a better global augmentation.

We prove this by comparing successive optima in the PAWL/PAWC growth [1,2] from kk to k+1k+1, minimizing transport cost first and then rank length, the number of cyclic gaps crossed. Removing alternating-component groups with zero net cardinality change cannot increase the refined cost, leaving one minimum-net-cost augmenting path. In a refined optimum, an edge cannot pass over an inactive atom. If the augmentation crosses one of its own previously inactive endpoints, Angrick et al.'s endpoint exchange [3] removes a non-improving equal-cardinality exchange and shortens the arc. Rank length makes the shortening strict even at coincident locations or flat costs, forcing one optimal augmentation to stay in a single cell. The minimum refined cell increment therefore reaches the next optimum.

Having justified the updates, we recover their plans through PAWC's free-gap argument. Each cell retains a rank gap untouched by earlier updates, and a neighboring gap survives a merge; when only two inactive atoms remain, we keep a gap from the complementary cell. A surviving gap unwraps every selected cell, so we can recover a plan at any recorded cardinality by sorting the active sources and targets, using a virtual cut when the gap lies between coincident copies. Continuing to K=min⁡(n,m)K=\min(n,m) returns the full profile, while a solve for one penalty λ\lambda can stop when the next transport-cost increment reaches 2λ2\lambda.

[1] Chapel and Tavenard, PAWL, ICLR 2025.

[2] Kolouri, PAWC, arXiv 2026.

[3] Angrick et al., Computing All Optimal Partial p-Wasserstein Matchings on the Line, arXiv 2026.

Reviewer_aoqqOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies optimal partial transport between two sets of unit-mass points on a circle in unbalanced setup. It computes the minimum cost for every matching size using local updates and a common cut that unwraps the circular problem onto a line. The construction extends earlier circular partial-matching methods to convex distance costs and repeated locations, with exact guarantees and specialized complexity bounds. The paper also develops spherical sliced distances and reference-based representations and evaluates correctness.

Critical strengths
  1. The paper provides additional improvements over prior circular partial-transport methods. It extends the guarantees to convex costs and repeated locations.
  2. The validation checks costs and recovered matchings against exact solvers. It also reports runtime and memory use and compares with PAWC.
Critical weaknesses
  1. The contribution is incremental over existing circular partial-transport methods. The main theoretical additions concern convex costs and repeated locations.
  2. I could not find the implementation. Without the code and run commands, the reported speedups are hard to reproduce.
  3. The solver only supports equal point weights. This limits its use for weighted circular histograms. The abstract should state this restriction clearly.
Questions for authors
  1. What is the main obstacle to extending the method to unequal point weights?
  2. Which parts of the solver can run in parallel? Do you have timing results?
  3. Can you share the code and commands for the runtime experiments?
2 comments
AuthorsOpenReview ↗

Response to aoqq (part 1)

Thank you for your careful review and valuable suggestions.

Code and commands are needed to reproduce the timings.

Following your request for implementation, commands, and runtime experiments, we have prepared and include the anonymous package COPT_Code.zip. The README.md in COPT/ contains setup instructions and benchmark commands.

python src/fast/build.py
python benchmark.py profile

We compared COPT with a min-cost-flow solver that retains its residual network as mass increases, so both methods reuse work across cardinalities while returning the full quadratic profile and one requested plan. At n=m=512n=m=512, COPT is 129--699 times faster across five families (Appendix B). We also compared the methods for one penalty, where COPT is 37--178 times faster than sparse flow at n=m=2048n=m=2048 and λ=10/n2\lambda=10/n^2 across four families, with comparable times on separated supports. Both workloads run with python benchmark.py flow.

The contribution appears incremental.

We appreciate your careful comparison with PAWL/PAWC [1,2] and Angrick et al. [3], whose ideas are important foundations of our method. Building on those works, we establish the circular optimality and recovery guarantees needed for convex costs and coincident observations. The mathematical difficulty is that the line theory assumes an ordering that must first be justified on the circle for the chosen cost, which can change the optimal cut [4]. PAWC establishes this structure for W1W_1; its intermediate common-cut statement for arbitrary nested balanced sets does not extend to squared cost (Appendix C.1). Even on distinct balanced supports with kk atoms per measure and a unique W1W_1 optimum, every W1W_1-optimal cut can have quadratic line cost approaching kk times the circular optimum (Appendix C.2).

We resolve the ordering problem by proving circular locality first (Lemma 1), adapting Angrick et al.'s endpoint argument and using rank refinement to keep the shortening strict when observations coincide or costs are flat. PAWC's free-gap construction can then recover the complete optimal history through one ordinary or virtual cut (Proposition 1). In the tied quadratic example of Section 4.3, full transport costs at least 3/83/8 at every ordinary cut, while a virtual cut attains 1/41/4, so allowing virtual cuts is necessary for the recovery guarantee. We use Angrick et al.'s interval tools for integer-power acceleration after establishing these circular guarantees.

We then tested whether solving the nonlinear objective improves task performance, holding transported mass fixed on USGS. Quadratic fitting lowers mean error over 20--40% uniform contamination by 18.9%, and quadratic-optimal plans improve the fit under either update rule (Table 1). To test whether the gain survives its computational cost, we also allowed 180 seconds of warmed USGS fitting per cost through COPT. Using each cost for both transport and updates, quadratic fitting lowers mean error over 20--40% contamination by 18.5%, improving all eight new seeds at each level despite about 9% fewer updates (Appendix K.10).

What prevents support for unequal weights?

Weighted circular histograms are a natural use case, as you point out, and the obstacle to a direct weighted update is that our current update uses an atom's whole mass when it becomes active. An atom of weight two could still send mass to a later target after transporting its first unit, so extending this update to weighted locations requires residual capacities in place of the active/inactive distinction.

We use repeated support to obtain a weighted reduction without altering the update, allowing coincident copies to be assigned independently so that one weighted location can send mass to several targets. For ai=qria_i=q r_i and bj=qsjb_j=q s_j, with common q>0q>0 and nonnegative integer counts, we replace each location by the corresponding number of copies. With expanded count Nq=∑iri+∑jsjN_q=\sum_i r_i+\sum_j s_j and profile Ck∘C_k^\circ, the weighted penalized value is

qmin⁡k{Ck∘+λ(Nq−2k)}.q\min_k\{C_k^\circ+\lambda(N_q-2k)\}.

Min-cost-flow integrality proves that scaling the copy solution by qq, without rescaling λ\lambda in the copy problem, recovers the weighted optimum. Our chroma experiment already uses unequal bin counts on twelve pitch classes represented by 72 unit atoms. To check the reduction on these inputs, we compared eight predetermined pairs with compact LPs and obtained agreement at every tested mass and penalty, including interpolation between grid masses and positive-cost fractional flows (Appendix A.6).

We state the reduction in Section 4.4 with complexity in NqN_q, since using copies does not provide a bound in the number of bins alone. Appendix A.6 proves a controlled approximation for arbitrary weights, and we have made the common-atom-weight assumption clear in the abstract.

AuthorsOpenReview ↗

Response to aoqq (part 2)

Which parts can run in parallel, and how fast?

To answer your timing question, we parallelized batches of pairwise comparisons, since the pairs do not share a profile state. Within a profile, each augmentation depends on the preceding one, so sorting, interval construction and heap updates remain serial. The table reports median batch times after warmup, in milliseconds.

Quadratic-cost workloadPairsSerialFour workersSpeedup
Uniform, n=m=256n=m=2566412.734.802.65×2.65\times
Uniform, n=m=4096n=m=409664275.5980.943.40×3.40\times
Separated supports, n=m=4096n=m=409632328.2491.913.57×3.57\times

The measured batch includes dispatch, full profiles, one recovered plan per pair and serialization, after pool setup and an initial batch. Including startup raises the four-worker time for the 4,096-atom uniform batch to 797.6 ms, against 277.1 ms serially, so the gain applies when workers can be reused across batches. Appendix B reports every worker count and agreement with serial computation; run the three workloads with python benchmark.py parallel.

[1] Chapel and Tavenard, PAWL, ICLR 2025.

[2] Kolouri, PAWC, arXiv 2026.

[3] Angrick et al., Computing All Optimal Partial p-Wasserstein Matchings on the Line, arXiv 2026.

[4] Rabin, Delon and Gousseau, Transportation Distances on the Circle, JMIV 2011.

Reviewer_JQUWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces Circular Optimal Partial Transport (COPT), a method for efficiently matching two sets of points on a circle while allowing some points to remain unmatched. It builds upon the recently published PAWC algorithm, which already introduced an efficient way to find optimal matchings for all possible numbers of matched points. The main novelty of COPT is extending PAWC beyond its original restrictions; it allows for convex radial costs and repeated support. The paper provides theoretical guarantees: an O(Nlog⁡N+K2)O(N\log N+K^2) algorithm for general convex costs where K = min(n,m), N = n + m, n = number of points in the first set, and m = number of points in the second set. There is faster O(Nlog⁡N)O(N\log N) and O(pNlog⁡2N)O(pN\log^2N) algorithms presented for linear and fixed integer-power costs, respectively. The approach presented also applies the approach to spherical data and develops representations for comparing distributions. Experiments evaluate computational efficiency and demonstrate applications in shape matching, image retrieval, and spherical data analysis.

Critical strengths

Meaningful extension of prior work. The paper extends PAWC to general convex transport costs and repeated point locations, supported by theoretical guarantees. This broadens the range of circular matching problems that can be solved exactly.

The method computes optimal matching costs for all possible numbers of matched pairs in a single run, with near-linear complexity for linear and fixed integer-power costs. The experiments show substantial speedups over approaches that repeatedly solve matching problems, although performance is comparable to PAWC in their shared setting.

The paper evaluates the method across different input configurations and applications, including shape matching, image retrieval, and spherical data. These experiments provide evidence of practical usefulness, although they do not always isolate the benefits of the proposed extensions over existing methods.

Clear writing and presentation. And I do want to stress this. The paper is well organized and clearly written. The theoretical results, algorithmic ideas, and relationship to prior work are explained clearly, making the contributions relatively easy to assess.

Critical weaknesses

COPT builds or expands directly on PAWC, which already introduced the key approach of computing optimal matchings for all possible numbers of matched pairs. The main contributions are extensions to more general costs (convex function of geodesic distance) and repeated point locations, while the faster evaluation of polynomial costs adapts existing techniques. This limits the degree of algorithmic novelty, particularly given the comparable performance to PAWC in their shared setting.

Many experiments primarily demonstrate the advantages of partial matching over conventional transport methods, rather than the added value of COPT's extensions. In several applications, linear costs already perform competitively, and the practical importance of handling repeated locations is not strongly established. Furthermore, the general convex-cost algorithm has potentially quadratic complexity, so the strongest efficiency guarantees apply only to specific cost functions such as the linear. These limitations make the practical significance of the broader framework less convincing.

Questions for authors

These are all clarification requests.

For the proposed algorithm, it is assumed equal-weight atoms. This reduces the computational problem to one-to-one partial matching. What is actually the main benefit of framing the method as optimal partial transport rather than as a partial assignment problem? In particular, which theoretical or practical advantages come from the transport formulation, given that the algorithm does not currently support arbitrary atom weights?

PAWC already provides the main approach for computing the complete matching profile, while the faster treatment of integer-power costs builds on Angrick et al. (2026). Which parts of the extension to convex costs require fundamentally new algorithmic or theoretical insights, beyond adapting these existing results?

In several experiments, linear transport costs perform comparably to or better than quadratic costs. Can the authors identify experimental settings where the proposed extension beyond linear costs provides a clear and consistent advantage over PAWC?

In Appendix B (p. 24, lines 1275–1284) it is reported that virtual cuts, i.e., cuts that split coincident points between the two ends of the unwrapped circle, are needed only in a small fraction of the tested cases and are unnecessary at the validation-selected penalties in the reported applications. Could the authors clarify in which practical settings virtual cuts provide a meaningful advantage in matching quality?

5 comments
AuthorsOpenReview ↗

Response to JQUW (part 1)

Thank you for your careful review and insightful questions about the benefits of partial transport and the broader cost class. Comparisons with balanced OT alone cannot answer your question about PAWC, so we added a controlled comparison for that purpose.

Q3. Where do nonlinear costs offer a clear advantage over W1W_1?

We agree that the broader cost class needs both an application-level motivation and evidence of benefit. In circular OT, Rabin et al. [1] compare powers and Huber costs according to the expected position and weight perturbations. In quadratic reference constructions such as LCOT [2] and LOPT [3], the representation itself requires squared-distance optima. Supporting these objectives requires more than tuning the mass penalty, because λ(N−2k)\lambda(N-2k) is constant across plans of cardinality kk and cannot change their relative preference.

To test whether this choice improves fitting beyond the benefit of discarding clutter, we returned to the USGS task from the submission. Following PAWC's target-side design [4], we used 500 particles, 625 targets and 32 shared slices, retaining 500 targets per slice under either cost. We evaluated PAWC's W1W_1 objective and the quadratic objective through COPT, crossing the plan cost with the update loss so that we could also test the plan choice while holding the update rule fixed. The table reports mean held-out chordal energy after 8,000 updates, in 10−310^{-3} units.

ContaminationW1W_1 plan, W1W_1 updateW1W_1 plan, quadratic updateQuadratic plan, W1W_1 updateQuadratic plan, quadratic update
0%1.2182.1611.3031.909
10%0.4100.4070.5360.540
20%1.4261.6500.9170.833
30%6.3786.9994.5424.811
40%15.73216.57112.84513.450

When each cost is used for both plan and update (first and last columns), quadratic fitting lowers error by 41.6%, 24.6% and 14.5% at 20%, 30% and 40% contamination, improving every seed at each level. Across these levels the reduction is 18.9%, with paired change −1.481 [−1.603,−1.359]×10−3-1.481\,[-1.603,-1.359]\times10^{-3}. Earlier disjoint evaluation cohorts also favor quadratic fitting (Appendix K.10).

Holding each update rule fixed in turn, we find that quadratic-optimal plans lower mean error over these levels by 22.2% with W1W_1 updates, −1.744 [−1.910,−1.579]×10−3-1.744\,[-1.910,-1.579]\times10^{-3}, and 24.3% with quadratic updates, −2.042 [−2.177,−1.907]×10−3-2.042\,[-2.177,-1.907]\times10^{-3}. The intervals are paired 95%, and all sixteen seeds improve at each level under both rules, with all four arms selecting rate 0.005 on validation data. This improvement under either update rule supports the benefit of optimizing the transport plan. Indeed, quadratic plans with W1W_1 updates have the lowest five-level mean, 4.029, and lead at 30% and 40%, so quadratic updates are not themselves the best choice throughout.

The low-contamination rows favor W1W_1, both on clean data and at 10%. Under this fixed quota, even a clean batch discards 125 genuine targets, so changing contamination also changes the retained composition and optimization trajectory. We further examined the role of the surplus targets and the outlier distribution in eight-seed comparisons, which favor W1W_1 when no surplus is available or the outliers form a concentrated cluster.

To test whether the fitting gain survives the extra computation, we gave each cost 180 seconds of warmed optimization on USGS, using COPT for both. Quadratic fitting lowers mean error over 20--40% uniform contamination by 18.5%, improving all eight new seeds at each of these three levels despite completing about 9% fewer updates, with all five levels reported in Appendix K.10.

These changes in preference led us to select one Huber configuration on validation data across all five uniform-contamination levels, then test it on sixteen further seeds against W1W_1 with its own validation-selected rate at the fixed quota. Mean USGS test error over those levels falls by 14.6%, with improvement in every seed average (Appendix K.10).

What practical benefit remains when the general-cost bound is quadratic?

We agree that the general O(Nlog⁡N+K2)O(N\log N+K^2) bound is a practical limitation, while the O(pNlog⁡2N)O(pN\log^2N) bound covers every fixed integer power p≥2p\ge2, including squared cost. For other convex costs, we tested whether profile reuse saves work when selecting a penalty. On 324 validation palette pairs, a 64-penalty Huber grid takes 0.030 s from shared profiles, against 1.12 s for repeated stopped solves and 0.502 s for cached assignment. Appendix B verifies that this workload uses Huber's nonquadratic region.

AuthorsOpenReview ↗

Response to JQUW (part 2)

Q2. What is new beyond PAWC and Angrick et al.?

We appreciate your careful comparison with PAWL/PAWC [4,5] and Angrick et al. [6], whose ideas are important foundations of our method. Building on those works, we establish globally optimal circular augmentations for a chosen convex cost and tied support, with the constructed plans at every cardinality recovered from one ordinary or virtual cut (Lemma 1 and Proposition 1).

A line argument requires a cut that supports the chosen cost, which cannot in general be obtained by running PAWC for W1W_1 and reusing its cut. Appendix C.1 explains why PAWC's intermediate shared-cut statement for arbitrary nested balanced sets cannot be transferred to squared cost. Appendix C.2 constructs distinct supports with kk atoms per measure and a unique W1W_1 optimum for which the full-cardinality quadratic line cost at every W1W_1-optimal cut approaches kk times the circular optimum. The factor is sharp, so choosing another optimal W1W_1 cut cannot resolve the difficulty.

We prove locality before choosing a cut by adapting Angrick et al.'s endpoint exchange directly to circular arcs, showing that a minimum-net-cost augmentation from a refined optimum cannot cross one of its previously inactive endpoints. Such a crossing would permit removal of a non-improving equal-cardinality exchange while strictly shortening the refined arc; rank length preserves this strictness when coordinates or costs tie. One optimal augmentation consequently lies in a cell, where Monge sorting attains its cost. Choosing the minimum refined cell increment reaches the next global optimum, after which PAWC's free-gap induction recovers a common ordinary or virtual cut for the history. The locality and common-cut proofs were already in the submitted Appendices A.3--A.4; Angrick et al.'s interval tools accelerate integer-power queries but are not needed for correctness.

AuthorsOpenReview ↗

Response to JQUW (part 3)

Q4. Why are virtual cuts useful if the selected penalties do not require them?

Your reading of the selected-penalty examples is correct. We include virtual cuts to recover the full profile without perturbing quantized data, since a nonlinear optimum can require coincident copies at both ends of the unwrapped interval. Our chroma inputs place 72 atoms on twelve pitch classes, and 184 of 216 Flowers database palettes repeat coordinates.

We illustrate the obstruction in Section 4.3 using X=(0,0,1/4,3/4)X=(0,0,1/4,3/4) and Y=(1/4,1/2,1/2,3/4)Y=(1/4,1/2,1/2,3/4). With squared cost, a virtual cut recovers the full transport cost 1/41/4, while every ordinary cut costs at least 3/83/8, so even searching every ordinary support gap can miss the optimum. This obstruction depends on the cost, since an ordinary optimal cut exists for W1W_1 at each chosen cardinality, including ties (Appendix B).

To assess its practical effect, we compared ordinary and virtual cuts on the chroma data as the penalty increases. Ordinary cuts attain the optimum at the selected penalty 0.004, but miss it on 177 and 179 of 5,688 pairs at penalties 0.032 and 0.5, with maximum excesses of 18.6% and 42.3%. The benefit here is recovering optimal profile values at larger transported masses, not higher retrieval accuracy. Tie-aware top-1 accuracy is equal, and we no longer count the submitted appendix's one-to-four top-1 changes as gains because they disappear under that scoring. Appendix B also explains why ordinary cuts suffice at the selected Flowers penalties.

Q1. What does OPT add when equal-weight inputs reduce to partial assignment?

For the common-weight inputs you ask about, the computation is indeed partial assignment; we use OPT to compare finite measures while allowing mass to be discarded and retaining metric structure. Bai et al.'s TV penalty [7] leads to min⁡k{Ck∘+λ(N−2k)}\min_k\{C_k^\circ+\lambda(N-2k)\}, whose ppth root is a metric for power costs, unlike a general fixed-mass partial discrepancy. We use this property in the spherical metric and full reference construction (Appendix K.1 and Proposition 2).

The measure formulation also lets us treat count histograms and rational weights through a common quantum, including split flows (Appendix A.6). For arbitrary weights, rounding discards mass Δ\Delta and changes the optimum by at most λΔ\lambda\Delta; the recovered plan is within 2λΔ2\lambda\Delta on the original inputs, with complexity measured in the expanded count. The penalty has a direct geometric interpretation as well, since an edge costing more than 2λ2\lambda can be deleted at lower cost. For power costs this limits transported distances to (2λ)1/p(2\lambda)^{1/p}; at equal total mass the value equals balanced transport capped at 2λ2\lambda, as in thresholded EMD (Pele and Werman [8]).

[1] Rabin, Delon and Gousseau, Transportation Distances on the Circle, JMIV 2011, Section 3.

[2] Diaz Martin et al., LCOT, ICLR 2024.

[3] Bai et al., Linear Optimal Partial Transport Embedding (LOPT), ICML 2023.

[4] Kolouri, PAWC, arXiv 2026.

[5] Chapel and Tavenard, PAWL, ICLR 2025.

[6] Angrick et al., Computing All Optimal Partial p-Wasserstein Matchings on the Line, arXiv 2026.

[7] Bai et al., Sliced Optimal Partial Transport (SOPT), CVPR 2023.

[8] Pele and Werman, Fast and Robust Earth Mover's Distances, ICCV 2009.

Comments on the paper

2 comments
AuthorsOpenReview ↗

To all reviewers and AC (part 1)

We thank the reviewers for their careful feedback. Although we recognize the maximally diverse(!) set of scores on our initial draft, we have uploaded a revised draft of our manuscript - plus a .zip of our code - to OpenReview, and, together with responses to individual reviewers below, we hope that this helps clarify our manuscript's contributions and addresses the constructive criticisms offered by the reviewers.

To recap the contribution/framing of our paper: we develop a general circular counterpart to the line theory of TV-penalized optimal partial transport for observations with missing content or clutter. Circular transport already supports spherical distribution learning through great-circle slicing (Bonet et al., 2023) and efficient comparison and representation learning through the LCOT embedding (Díaz Martín et al., 2024). Extending these constructions to incomplete observations requires optimal partial plans for the chosen geometry, including the quadratic geometry widely studied in the transport literature and used, for example, in LOPT, LCOT and LSSOT (Bai et al., 2023; Liu et al., 2025). For atoms of equal weight, COPT establishes optimality and complexity guarantees for convex radial costs and repeated support, including the complete quadratic profile in O(Nlog⁡2N)O(N\log^2N) time. We demonstrate these uses through Spherical Sliced COPT and the Linear COPT embedding, studying their metric properties, fitting accuracy and computational cost.

PAWL and PAWC developed full-profile constructions on the line and circle, respectively (Chapel and Tavenard, 2025; Kolouri, 2026). Our algorithm builds directly on PAWC’s circular cells, greedy profile growth and free-gap construction, established for W1W_1 on distinct support. We establish global optimality across the broader cost and support class through a rank-refined circular locality theorem. PAWC’s intermediate common-cut lemma for arbitrary nested sets does not extend to squared cost. Our proof instead adapts Angrick et al.’s endpoint argument to circular arcs, with rank refinement handling coincident observations and flat cost regions without perturbing the data. PAWC’s free-gap construction then produces an ordinary or virtual cut valid for the entire profile, while Angrick et al.’s interval tools accelerate integer-power evaluation. The locality and common-cut proofs were already part of the submitted Appendices A.3–A.4.

In our revision, we have substantially expanded the experiments to test whether the broader theory brings practical benefits. The new evidence addresses cost choice, optimization time and profile computation, alongside revisions explaining the method and its treatment of weighted data.

  • Cost choice. The reviewers asked whether nonlinear costs offer an advantage beyond partial transport itself. We first compare W1W_1 and quadratic fitting at fixed transported mass, using each cost for both transport and updates. After 8,000 updates on USGS, quadratic fitting reduces mean held-out chordal energy over 20–40% uniform contamination by 18.9%, improving all sixteen paired-seed averages. We then hold the update rule fixed to test the contribution of the transport plans. Quadratic-optimal plans reduce mean error over these levels by 22.2% under W1W_1 updates and 24.3% under quadratic updates, improving all sixteen seeds at each of the three levels under either rule (Table 1 and Appendix K.10).

  • Computation and cost selection. We next test whether the fitting advantage extends beyond USGS and survives the additional computational cost. On a five-component spherical mixture, quadratic-optimal plans lower mean error by 20.2% with quadratic updates held fixed over 20–40% contamination, improving all sixteen seed averages. On USGS, we gave each cost 180 seconds of warmed optimization through COPT, using each cost for both transport and updates. Quadratic fitting lowers mean error over 20–40% uniform contamination by 18.5%, improving all eight new seeds at each level despite completing about 9% fewer updates. We also evaluate choosing the cost from validation data. In a further USGS study, one selected Huber configuration lowers mean test energy over the five uniform-contamination levels by 14.6% against W1W_1 with its own validation-selected rate, holding the quota fixed across costs. All sixteen further seed averages improve. Appendix K.10 reports the complete conditions and per-level results.

AuthorsOpenReview ↗

To all reviewers and AC (part 2)

  • Profile runtime. A full-profile comparison should allow the baseline to reuse work as transported mass increases. We therefore add a min-cost-flow solver that retains its residual network throughout the computation. Both methods return the complete quadratic profile and one requested plan; at n=m=512n=m=512, median speedups for COPT are 129–699 times across five input families. Appendix B reports this comparison alongside the cut-sweep and assignment benchmarks.

  • Method explanation. The reviewers asked for a self-contained explanation of why local updates solve the global problem. Section 4 now develops a complete cell update, its optimality argument and plan recovery in that order. Sections 5–6 describe the experimental tasks alongside their results and develop the spherical and linear constructions with their definitions, guarantees and the controlled fitting comparison. Independent checks cover 170,900 profiles and 709,404 cardinalities, including cases requiring virtual cuts. Every tested profile value, recovered plan cost and common-cut lift agrees with an integer-cost oracle (Appendix B).

  • Weighted inputs and implementation. Section 4.4 and Appendix A.6 derive the common-quantum reduction from weighted histograms to repeated atoms, including split flows, complexity in the expanded count and approximation bounds for arbitrary weights. Our chroma experiment already uses this representation, expressing unequal histogram counts as repeated atoms on twelve pitch classes. Following the request for implementation and runtime commands, we have prepared COPT_Code.zip for the Supplementary Material, with instructions in its README.md.

Bonet et al., Spherical Sliced-Wasserstein, ICLR 2023.

Diaz Martin et al., LCOT, ICLR 2024.

Bai et al., Linear Optimal Partial Transport Embedding (LOPT), ICML 2023.

Liu et al., Linear Spherical Sliced Optimal Transport (LSSOT), ICLR 2025.

Chapel and Tavenard, PAWL, ICLR 2025.

Kolouri, PAWC, arXiv 2026.

Angrick et al., Computing All Optimal Partial p-Wasserstein Matchings on the Line, arXiv 2026.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.