Quantization-based Bounds on the Wasserstein Metric

Amit Moscovich; Jonathan Bobrutsky

REVIEW 2 major objections 5 minor 27 references

Quantization-based Bounds on the Wasserstein Metric

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that the Wasserstein distance between discrete measures on a regular grid can be strictly bounded from above and below by solving much smaller optimal transport problems on a coarsened grid, then upscaling and…

desk verdict A genuinely new and correct upper bound for grid Wasserstein, with a fixable zero-mass gap and a slightly overstated abstract; worth refereeing. read the letter →

arxiv 2506.00976 v1 pith:ADU5AFVQ submitted 2025-06-01 cs.LG stat.COstat.ML

Jonathan Bobrutsky , Amit Moscovich This is my paper

classification cs.LGstat.COstat.ML

keywords Wassersteinmetricoptimaltransportdiscretemeasuresongridsquantizationboundsdualitygapc-transformcoarsegridcomputational

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the $p$-Wasserstein distance $W_p(\mu,\nu)$ between two discrete measures on a regular grid can be bracketed from above and below using only coarse-grid optimal transport, with the gap between the two bounds controlled by an upscaling and correction step. If the construction is correct, practitioners get strict guarantees on the true metric at a fraction of the cost: the authors report speedups of 10--100$\times$ over entropy-regularized optimal transport on standard benchmark images, with typical relative error below 2%. The upper bound is obtained by averaging the ground cost against the product measure inside each coarse cell, while the lower bound comes from interpolating coarse dual potentials and tightening them with the $c$-transform.

What carries the argument

The central object is the marginally weighted coarse cost matrix $\bar{C}_{k\ell}$, which averages the true cost $\rho(x,y)^p$ inside each pair of coarse cells $X_k \times Y_\ell$ with weights given by the product measure $\mu(x)\nu(y)$, normalized by the cell masses. It makes the coarse problem exact: the cost of any coarse coupling under $\bar{C}$ equals the cost of its natural lift to a fine coupling under $C$, so the minimal coarse cost overshoots the true minimum. The second load-bearing mechanism is the $c$-transform on interpolated dual potentials: starting from any approximate potential on the fine grid, taking $f^c_j = \min_i C_{ij} - f_i$ and $f^{cc}_i = \min_j C_{ij} - f^c_j$ produces an admissible pair $(f^{cc}, f^c)$, and every admissible pair certifies a lower bound on the primal optimum.

What would settle it

Take two sparse measures on a fine grid, coarsen them so that at least one coarse cell has zero mass in one measure, and run the weighted-cost upper bound: the formula divides by zero. If the construction is meant to apply to all discrete measures on grids, this counterexample forces either an explicit empty-cell convention or a restriction to positive-density measures.

Watch

Extended reading notes

Core claim

The central discovery is that a Kantorovich problem on a coarsened grid can be modified so that its exact solution certifies a bound on the full-resolution problem. Theorem 3.4 proves that the optimal transport loss under the marginally weighted coarse cost $\bar{C}_{k\ell} = \frac{1}{\mu(X_k)\nu(Y_\ell)} \sum_{x\in X_k, y\in Y_\ell} \rho(x,y)^p \mu(x)\nu(y)$ is an upper bound on the true loss $L_C(\mu,\nu)$, hence the coarse Wasserstein distance is at least $W_p(\mu,\nu)$. Proposition 3.9 proves that interpolating the optimal coarse Kantorovich potentials to the fine grid and taking their $c$-transform produces an admissible dual pair whose inner product with the measures is a lower bound on $L_C(\mu,\nu)$. A primal upscaling variant with weighted total variation marginal corrections gives a second upper bound, and a per-cell minimum cost gives a second lower bound, so the paper delivers two-sided strict bounds.

Load-bearing premise

The weighted-cost upper bound divides by the total mass in each coarse cell of both measures, so it is well defined only when every coarse cell carries strictly positive mass in both measures.

Editorial extensions

If this is right

For grid measures with side length $N$, the exact $W_p$ lies between two quantities computable from a coarse problem of side $N/\kappa$, so the cost and memory of certification scale with the coarse grid rather than the fine one.
The bounds are strict, so they can be used to certify approximation quality in machine learning applications such as generative modeling, image retrieval, and domain adaptation, where entropy-regularized OT only gives biased estimates.
The lazy $c$-transform evaluates the lower bound on demand without ever building the full $N^d \times N^d$ cost matrix, cutting memory from $\Theta(N^{2d})$ to $\Theta((N/\kappa)^{2d})$.
On benchmark images and cryo-EM density maps, the reported relative error stays below 2% for $\kappa=2$, with the dual upscaling lower bound computed in 0.2--2.2% of the exact solver's time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The construction likely extends to point clouds and graphs, as the paper hints, but the coarse-cell weighting needs a surrogate for the product measure when cells have zero mass.
The dual upscaling lower bound could be made adaptive by iterating between interpolation and $c$-transform tightening, trading runtime for tighter certificates.
A practical limitation follows from the weighted-cost formula: the upper bound is undefined for sparse measures with empty coarse cells, so an explicit convention such as merging empty cells or falling back to the min-cost bound would be needed before applying the method to sparse data.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main result is the weighted-cost upper bound (Thm 3.4): solving OT on the coarse grid with the marginally weighted cost \bar C gives a strict upper bound on the full-resolution W_p. I checked the proof and it works. The construction in Lemma C.1 (coupling via the trivial coupling weighted by a coarse coupling) is genuinely new as far as I know, and the min-cost lower bound plus the primal/dual upscaling variants are sensible extensions of known multiscale ideas. The paper is honest about limitations, and the experiments on DOTmark and EMDB are appropriate.

The biggest gap is a missing convention for zero-mass coarse cells. Eq. (15) divides by \mu(X_k)\nu(Y_\ell); when either cell is empty, \bar C is undefined. The proof of Thm 3.4 (Lemma C.1) has the same 0/0 issue. This is not fatal—the natural repair is to set \bar C_{k\ell}=0 on blocks where the product is zero, since no coarse coupling can put mass there, and the coupling in the proof becomes zero on those blocks. But the paper never says this, and the EMDB experiments mask density in a sphere, so empty coarse cells are real, not hypothetical. The theorem as stated is not well-defined for sparse grid measures, which are in scope. This should be fixed with one sentence and a short remark.

Two smaller things. The complexity table (Table 1) lists O(n^{3d}) time for the quantization bounds, but the dual upscaling lower bound requires a c-transform on the full grid, which costs O(N^{2d}) = O(\kappa^{2d} n^{2d}) time. The coarse OT dominates asymptotically, so the table is not wrong in order, but it omits a term that matters for the moderate n in the experiments. And the abstract's "<2% error" claim is only true for the best configurations; Table 2 shows several variants above that. It's a typical abstract overstatement, but worth flagging.

The proofs I read are correct and the paper does not fit parameters to make the bounds valid—the hyperparameters only affect tightness and runtime. I'd send this to a serious referee. It's a solid contribution to computational OT for grid data, with clear value for imaging and cryo-EM. With the zero-mass fix and a cleaned-up complexity table, it should be publishable.

Referee Report

2 major / 5 minor

Summary. This paper develops algorithms to compute upper and lower bounds on the p-Wasserstein distance between discrete probability measures supported on a regular grid. The approach coarsens the measures by sum-pooling into hypercubes, solves an optimal transport problem on the coarse grid with one of several specially constructed cost matrices (a marginal-weighted average cost, a local-min cost, or a center-based cost), and then upscales the coarse solution to the original grid. Upper bounds are obtained from the weighted-cost method or from primal upscaling followed by iterative proportional fitting with total-variation corrections; lower bounds come from the min-cost method or from dual upscaling with c-transformed interpolated potentials. The methods are evaluated on the DOTmark image benchmark and on 3D cryo-EM density maps, reporting 10x-100x speedups over entropy-regularized OT with approximation errors below 2% in many settings.

Significance. The paper addresses a practically important problem and offers a self-contained derivation of the bounds. The main constructions are elegant, and the proofs are largely correct, with no fitted parameters; the hyperparameters κ and ξ affect tightness and runtime but not validity. The upper bound via the marginally weighted coarse cost is a particularly nice idea, and the experimental study covers realistic 2D and 3D data. If the gaps identified below are repaired, the contribution would be valuable for applications such as cryo-EM alignment and image retrieval.

major comments (2)

[§3.2, Eq. (15), and Appendix C.2, Lemma C.1] The marginally weighted coarse cost \bar C_{k\ell} is undefined whenever \mu(X_k)\nu(Y_\ell)=0, since the denominator vanishes. The proof of Lemma C.1 constructs \pi_{\tilde\pi}(x,y) with the factor \tilde\pi_{k\ell}/(\mu(X_k)\nu(Y_\ell)), which is 0/0 on such blocks. Because \tilde\pi_{k\ell}=0 whenever the corresponding coarse row or column mass is zero, the construction can be repaired by defining \pi_{\tilde\pi}=0 and \bar C_{k\ell}=0 on those blocks, but the paper states no such convention. This is not a purely academic concern: the EMDB experiments in Appendix B.2 mask densities inside a sphere and then coarsen, producing coarse cells of zero mass; the reported weighted-cost upper bounds in Table 3 therefore rely on an unstated convention. Please add a explicit zero-mass convention to Eq. (15) and Lemma C.1, and either state Theorem 3.4 for all discrete measures on grids under that convention or restrict its scope accordingly.
[§4, Table 1, and Algorithm 5] The stated O(n^{3d}) time complexity for the quantization-based bounds omits the cost of the fine-grid c-transform in Eq. (27)-(28). The lazy c-transform requires computing g_j = min_i (\rho(x_i,x_j)^p - \hat f_i) and then f_i = min_j (\rho(x_i,x_j)^p - g_j), which naively costs O(N^{2d}). For the EMDB setting with N=16 and κ=4, this is O(16^6), which is 16 times larger than the coarse network-simplex bound O(n^6)=O(4^6); the omitted term can dominate exactly in the low-resolution regime used in the experiments. Asymptotically N^{2d} is lower order than n^{3d} for fixed κ, but the complexity analysis should either include the c-transform cost explicitly or state the assumptions under which it is negligible.

minor comments (5)

[Throughout] There are frequent typos, including 'Upsacling' in Figures 2-5 and Tables 2-4, and 'in in practice' in the Conclusion.
[§3.1] The text refers to 'Theorem 3.2' and 'Theorem 3.3' where the statements are Lemma 3.2 and Proposition 3.3; the cross-reference should be corrected.
[Appendix C.2] In the proof of Theorem 3.4, the references to 'Theorem C.1' and 'Theorem C.2' should be to 'Lemma C.1' and 'Lemma C.2', respectively.
[Algorithm 4] The kernel K is defined as the constant {κ^{-2d}} over t∈[κ]^{2d}; this is a scalar, not a spatially varying kernel. The notation is clear but a short remark that this corresponds to nearest-neighbor upsampling would help.
[§3.4] The proof of Theorem 3.7 cites 'Theorem 3.2' and 'Theorem 3.6' but these should be 'Lemma 3.2' and 'Lemma 3.6'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bounds follow by direct inequalities and admissible-coupling/potential constructions, with no fitted inputs or self-citation chains supporting the main results.

full rationale

The paper's central claims are self-contained derivations rather than circular restatements. Theorem 3.4 is proved by explicitly constructing an admissible fine coupling pi_tilde_pi from any coarse coupling, and Lemma C.2 shows the identity <pi_tilde_pi, C> = <tilde_pi, barC>; since L_C is a minimum over admissible couplings, evaluating any admissible coupling with the original cost gives an upper bound. This is a direct inequality, not a definitional equivalence. The lower bound in Theorem 3.5 follows from the pointwise inequality Cmin <= C, the primal upscaling upper bound in Theorem 3.7 follows from the triangle inequality plus weighted total variation control, and Proposition 3.9 uses the c-transform to produce an admissible dual pair, so every dual value is a valid lower bound. None of these arguments feed the target Wasserstein value back into the construction, and the hyperparameters kappa and xi affect tightness and runtime but not the validity of the inequalities. The self-citations in the paper (Rao et al., Kileel et al., and the ASPIRE package) appear only in related-work context and experimental tooling, not as premises of the main theorems, so they are not load-bearing. The only notable weakness is that the weighted-cost definition in Eq. (15) is undefined when a coarse cell has zero total mass in either measure, and no convention for empty cells is stated; this is a well-posedness and completeness gap for the experiments, not a circularity, and it does not change the fact that the derivation is logically independent of its inputs.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The methods rely on standard LP duality and the weighted TV inequality; no new entities are introduced. The hyperparameters kappa and xi affect tightness and speed but not the validity of the bounds.

free parameters (2)

kappa (coarsening scale factor) = 2 or 4 in experiments
Controls the trade-off between speed and tightness. Not fitted to data; does not affect validity of the bounds.
xi (IPF convergence threshold) = not specified numerically in the paper's experiments
Smaller values give tighter TV corrections. The paper does not report the chosen value, which affects the reported timings.

assumptions (4)

standard math Strong duality for the Kantorovich linear program (Eq. 4-5)
Used to define dual potentials and to prove the dual upscaling lower bound.
standard math Weighted total variation inequality W_p <= 2^(1-1/p) <w,|mu-nu|>^(1/p) (Eq. 11)
Basis for the TV correction terms in the upper bounds; cited to Villani (2009).
domain assumption Measures are discrete probability measures on a regular grid with side length divisible by kappa
The entire method relies on sum-pooling into hypercubes and defining center-based coarse grids.
standard math Sinkhorn's theorem for iterative proportional fitting converges to exact marginals in the limit
Used in the primal upscaling upper bound to adjust marginals; the stopping criterion is only approximate but TV corrections handle the residual.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantization-based Bounds on the Wasserstein Metric." pith.science (2026). https://pith.science/paper/ADU5AFVQ

@misc{pith2026250600976,
  author       = {Pith},
  title        = {Pith review of: Quantization-based Bounds on the Wasserstein Metric},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ADU5AFVQ}},
  note         = {Machine review of arXiv:2506.00976}
}

read the original abstract

The Wasserstein metric has become increasingly important in many machine learning applications such as generative modeling, image retrieval and domain adaptation. Despite its appeal, it is often too costly to compute. This has motivated approximation methods like entropy-regularized optimal transport, downsampling, and subsampling, which trade accuracy for computational efficiency. In this paper, we consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds. Focusing on discrete measures on regular grids, our approach involves formulating and exactly solving a Kantorovich problem on a coarse grid using a quantized measure and specially designed cost matrix, followed by an upscaling and correction stage. This is done either in the primal or dual space to obtain valid upper and lower bounds on the Wasserstein metric of the full-resolution inputs. We evaluate our methods on the DOTmark optimal transport images benchmark, demonstrating a 10x-100x speedup compared to entropy-regularized OT while keeping the approximation error below 2%.

Figures

Figures reproduced from arXiv: 2506.00976 by the authors.

**Figure 2.** Efficiency of Wasserstein Upper Bounds 10−3 10−2 10−1 100 Relative Time 10−3 10−2 10−1 100 Relative Error p = 1 10−3 10−2 10−1 100 Relative Time p = 2 Lower Bounds Dual Upsacling (κ = 2) Min-Cost (κ = 2) Dual Upsacling (κ = 4) Min-Cost (κ = 4) Dual Entropic Reg. (ε = 0.001N p ) Dual Entropic Reg. (ε = 0.004N p ) [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Efficiency of Wasserstein Lower Bounds 0 20 40 60 80 100 120 140 160 180 Rotation Angle (deg) 102 103 Wasserstein Distance Bounds p = 1 0 20 40 60 80 100 120 140 160 180 Rotation Angle (deg) 101 102 p = 2 Methods Weighted-Cost (κ2) Weighted-Cost (κ4) Primal Upsacling (κ2) Primal Upsacling (κ4) Primal Entropic Reg. (ε1) Primal Entropic Reg. (ε4) Dual Upsacling (κ2) Dual Upsacling (κ4) Min-Cost (κ2) Min-Cost (κ4) Dual… view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: Wasserstein distance bounds between rotated 3D density maps of the 80S ribosome. The [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Accuracy of Wasserstein Upper Bounds 5 10 15 20 25 30 35 Wp 10−3 10−2 10−1 100 Relative Error p = 1 5 10 15 20 25 30 35 40 Wp p = 2 Lower Bounds Dual Upsacling (κ = 2) Dual Upsacling (κ = 4) Dual Entropic Reg. (ε = 0.001N p ) Dual Entropic Reg. (ε = 0.004N p ) Min-Cost…

**Figure 6.** Figure 6: Accuracy of Wasserstein Lower Bounds. Negative-valued bounds are clipped to 0, evaluat [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]

**Figure 7.** Figure 7: Isosurfaces of 3D molecular densities from the Electron Microscopy Data Bank (EMDB). [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

**Figure 8.** Figure 8: Wasserstein-p metric and bounds between rotated 3D density maps of the molecules described in [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 14 canonical work pages

[1]

Lemma C.1.Let µ, νmeasures with set of admissible couplings Π(µ,ν) , the trivial coupling π⊗ , and ˜µand ˜νthe respective coarsened measures

1 p rJensen’s inequality <2 2− 2 p ξ 1 p rconvergence criteria 19 C.2 Proof of Theorem 3.4 First, let us consider the following lemma discussing a coupling constructed ad hoc using coarsened measures. Lemma C.1.Let µ, νmeasures with set of admissible couplings Π(µ,ν) , the trivial coupling π⊗ , and ˜µand ˜νthe respective coarsened measures. For any coupli...

work page 2009
[4]

Negative-valued bounds are clipped to 0, evaluat- ing as 100% relative error

Figure 6: Accuracy of Wasserstein Lower Bounds. Negative-valued bounds are clipped to 0, evaluat- ing as 100% relative error. 15 B Experiments B.1 DOTmark In this section we present additional figures and results evaluating the proposed Wasserstein bounds on the discrete optimal transport benchmark (DOTMark) [Schrieber et al., 2017] presented in the main ...

work page 2017
[6]

Negative-valued lower bounds are trivially clipped to 0, when evaluate in the benchmark. B.2 EMDB The Electron Microscopy Data Bank (EMDB) [wwPDB Consortium, 2024] is a repository of volumetric density maps that contains many interesting molecules that were reconstructed from cryogenic electron microscopy (cryo-EM) experiments. These reconstructions are e...

work page 2024
[10]

doi:10.1111/j.1467-8659.2011.02032.x

ISSN 01677055. doi:10.1111/j.1467-8659.2011.02032.x. E. F. Montesuma, F. M. N. Mboula, and A. Souloumiac. Recent Advances in Optimal Transport for Machine Learning.IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(02): 1161–1180, Feb

arXiv 2011
[15]

doi:10.1109/TCBB.2023.3327633

ISSN 1557-9964. doi:10.1109/TCBB.2023.3327633. G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V . Subramanian, A. Solomon, J. Gould, S. Liu, S. Lin, P. Berube, L. Lee, J. Chen, J. Brumbaugh, P. Rigollet, K. Hochedlinger, R. Jaenisch, A. Regev, and E. S. Lander. Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories ...

arXiv 2023
[16]

doi:10.1016/j.cell.2019.01.006

ISSN 1097-4172. doi:10.1016/j.cell.2019.01.006. J. Schrieber, D. Schuhmacher, and C. Gottschlich. DOTmark – A Benchmark for Discrete Optimal Transport.IEEE Access, 5:271–282,

doi:10.1016/j.cell.2019.01.006 2019
[17]

doi:10.1109/ACCESS.2016.2639065

ISSN 2169-3536. doi:10.1109/ACCESS.2016.2639065. S. Shirdhonkar and D. W. Jacobs. Approximate earth mover’s distance in linear time. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, June

work page arXiv 2016
[21]

doi:10.3389/fmicb.2022.870938

ISSN 1664-302X. doi:10.3389/fmicb.2022.870938. C. Villani.Optimal Transport, Old and New, volume 338 ofGrundlehren Der Mathematischen Wissenschaften. Springer, Berlin, Heidelberg,

work page arXiv 2022

Show all 27 references

[24]

doi:10.1093/nar/gkad1019

ISSN 0305-1048. doi:10.1093/nar/gkad1019. 12 A Algorithms Lower-bound based on entropic regularization described in Section 3.1. This method simply runs the iterative Sinkhorn algorithm an then returns the unregularized cost term of the dual solution to the entropic regulariza...

doi
[1967]

URL https: //projecteuclid.org/journals/pacific-journal-of-mathematics/volume-21/ issue-2/Concerning-nonnegative-matrices-and-doubly-stochastic-matrices/ pjm/1102992505.full

ISSN 0030-8730. URL https: //projecteuclid.org/journals/pacific-journal-of-mathematics/volume-21/ issue-2/Concerning-nonnegative-matrices-and-doubly-stochastic-matrices/ pjm/1102992505.full. M. Kusner, Y . Sun, N. Kolkin, and K. Weinberger. From Word Embeddings To Document Dis...
[2008]

doi:10.1109/CVPR.2008.4587662. 11 A. Singer and R. Yang. Alignment of density maps in Wasserstein distance.Biological Imaging, 4: e5, Jan

2008
[2009]

doi:10.1007/978- 3-540-71050-9

ISBN 978-3-540-71050-9. doi:10.1007/978- 3-540-71050-9. W. Wong, X.-c. Bai, A. Brown, I. S. Fernandez, E. Hanssen, M. Condron, Y . H. Tan, J. Baum, and S. H. Scheres. Cryo-EM structure of the Plasmodium falciparum 80S ribosome bound to the anti- protozoan drug emetine.eLife, 3...

doi
[2011]

doi:10.1145/2070781.2024192

ISSN 0730-0301. doi:10.1145/2070781.2024192. J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang. JAX: Composable transformations of Python+NumPy programs,
[2013]

doi:10.1038/nsmb.2711

ISSN 1545-9985. doi:10.1038/nsmb.2711. G. Beugnot, A. Genevay, K. Greenewald, and J. Solomon. Improving approximate optimal transport distances using quantization. InProceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 290–300. PMLR, Dec

doi
[2014]

doi:10.7554/eLife.03080

ISSN 2050-084X. doi:10.7554/eLife.03080. G. Wright, J. Andén, V . Bansal, J. Xia, C. Langfield, J. Carmichael, K. Sowattanangkul, R. Brook, Y . Shi, A. Heimowitz, G. Pragier, I. Sason, A. Moscovich, Y . Shkolnisky, and A. Singer. ComputationalCryoEM/ASPIRE-Python: V0.13.2. Zenodo, Mar

doi
[2015]

doi:10.1145/2766963. S. Stagnoli, F. Peccati, S. R. Connell, A. Martinez-Castillo, D. Charro, O. Millet, C. Bruzzone, A. Palazon, A. Ardá, J. Jiménez-Barbero, J. Ereño-Orbea, N. G. A. Abrescia, and G. Jiménez- Osés. Assessing the Mobility of Severe Acute Respiratory Syndrome C...

doi
[2016]

doi:10.1038/nature16940

ISSN 1476-4687. doi:10.1038/nature16940. G. Peyré and M. Cuturi. Computational Optimal Transport: With Applications to Data Science. Foundations and Trends® in Machine Learning, 11(5-6):355–607,

doi
[2017]

doi:10.1109/TPAMI.2016.2615921

ISSN 1939-3539. doi:10.1109/TPAMI.2016.2615921. M. Cuturi. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. InAdvances in Neural Information Processing Systems, volume

1939
[2018]

URL https://openaccess.thecvf.com/content_cvpr_ 2018/html/Deshpande_Generative_Modeling_Using_CVPR_2018_paper.html. J. Feydy, P. Roussillon, A. Trouvé, and P. Gori. Fast and Scalable Optimal Transport for Brain Tractograms, July

2018
[2019]

ISSN 1935-8237, 1935-

1935
[2020]

URL https://proceedings.neurips.cc/paper/2020/hash/ f52a7b2610fb4d3f74b4106fb80b233d-Abstract.html. M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein Generative Adversarial Networks. InProceed- ings of the 34th International Conference on Machine Learning, pages 214–223. PMLR, July

2020
[2021]

doi:10.1007/s00041-021-09879-2

ISSN 1069-5869, 1531-5851. doi:10.1007/s00041-021-09879-2. P. Knopp and R. Sinkhorn. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343–348, Jan

doi
[2022]

ISBN 978-1-66546-946-3

IEEE. ISBN 978-1-66546-946-3. doi:10.1109/CVPR52688.2022.00060. N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal Transport for Domain Adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(9):1853–1865, Sept

2022
[2023]

doi:10.1002/pro.4792

ISSN 1469-896X. doi:10.1002/pro.4792. Q. Mérigot. A Multiscale Approach to Optimal Transport.Computer Graphics Forum, 30(5): 1583–1592, Aug

doi
[2024]

doi:10.1017/S2633903X24000059

ISSN 2633-903X. doi:10.1017/S2633903X24000059. J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas. Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains. ACM Transactions on Graphics, 34(4):66:1–66:11,

doi
[2025]

doi:10.1109/TPAMI.2024.3489030

ISSN 0162-8828. doi:10.1109/TPAMI.2024.3489030. T. H. D. Nguyen, W. P. Galej, X.-c. Bai, C. Oubridge, A. J. Newman, S. H. W. Scheres, and K. Nagai. Cryo-EM structure of the yeast U4/U6.U5 tri-snRNP at 3.7 Å resolution.Nature, 530(7590): 298–302, Feb

2024
[8245]

doi:10.1561/2200000073. R. Rao, A. Moscovich, and A. Singer. Wasserstein K-Means for Clustering Tomographic Pro- jections. InMachine Learning for Structural Biology Workshop, Neural Information Process- ing Systems (NeurIPS), pages 1–12,

doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Lemma C.1.Let µ, νmeasures with set of admissible couplings Π(µ,ν) , the trivial coupling π⊗ , and ˜µand ˜νthe respective coarsened measures

1 p rJensen’s inequality <2 2− 2 p ξ 1 p rconvergence criteria 19 C.2 Proof of Theorem 3.4 First, let us consider the following lemma discussing a coupling constructed ad hoc using coarsened measures. Lemma C.1.Let µ, νmeasures with set of admissible couplings Π(µ,ν) , the trivial coupling π⊗ , and ˜µand ˜νthe respective coarsened measures. For any coupli...

work page 2009

[2] [4]

Negative-valued bounds are clipped to 0, evaluat- ing as 100% relative error

Figure 6: Accuracy of Wasserstein Lower Bounds. Negative-valued bounds are clipped to 0, evaluat- ing as 100% relative error. 15 B Experiments B.1 DOTmark In this section we present additional figures and results evaluating the proposed Wasserstein bounds on the discrete optimal transport benchmark (DOTMark) [Schrieber et al., 2017] presented in the main ...

work page 2017

[3] [6]

Negative-valued lower bounds are trivially clipped to 0, when evaluate in the benchmark. B.2 EMDB The Electron Microscopy Data Bank (EMDB) [wwPDB Consortium, 2024] is a repository of volumetric density maps that contains many interesting molecules that were reconstructed from cryogenic electron microscopy (cryo-EM) experiments. These reconstructions are e...

work page 2024

[4] [10]

doi:10.1111/j.1467-8659.2011.02032.x

ISSN 01677055. doi:10.1111/j.1467-8659.2011.02032.x. E. F. Montesuma, F. M. N. Mboula, and A. Souloumiac. Recent Advances in Optimal Transport for Machine Learning.IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(02): 1161–1180, Feb

arXiv 2011

[5] [15]

doi:10.1109/TCBB.2023.3327633

ISSN 1557-9964. doi:10.1109/TCBB.2023.3327633. G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V . Subramanian, A. Solomon, J. Gould, S. Liu, S. Lin, P. Berube, L. Lee, J. Chen, J. Brumbaugh, P. Rigollet, K. Hochedlinger, R. Jaenisch, A. Regev, and E. S. Lander. Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories ...

arXiv 2023

[6] [16]

doi:10.1016/j.cell.2019.01.006

ISSN 1097-4172. doi:10.1016/j.cell.2019.01.006. J. Schrieber, D. Schuhmacher, and C. Gottschlich. DOTmark – A Benchmark for Discrete Optimal Transport.IEEE Access, 5:271–282,

doi:10.1016/j.cell.2019.01.006 2019

[7] [17]

doi:10.1109/ACCESS.2016.2639065

ISSN 2169-3536. doi:10.1109/ACCESS.2016.2639065. S. Shirdhonkar and D. W. Jacobs. Approximate earth mover’s distance in linear time. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, June

work page arXiv 2016

[8] [21]

doi:10.3389/fmicb.2022.870938

ISSN 1664-302X. doi:10.3389/fmicb.2022.870938. C. Villani.Optimal Transport, Old and New, volume 338 ofGrundlehren Der Mathematischen Wissenschaften. Springer, Berlin, Heidelberg,

work page arXiv 2022