Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling

Benjamin J Raphael; Julian Gold; Peter Halmos; Xinhao Liu

REVIEW 2 major objections 4 minor 58 references

Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper establishes that low-rank optimal transport can be solved exactly by optimizing a latent-coupling factorization into three smaller OT problems, and gives an O(1/N) coordinate mirror-descent algorithm (FRLC) that stays feasible…

desk verdict A genuinely useful low-rank OT algorithm with a real proof gap in its convergence guarantee; worth refereeing once the authors fix Proposition E.5. read the letter →

arxiv 2411.10555 v1 pith:ZDRENGO3 submitted 2024-11-15 cs.LG cs.AIstat.ML

Peter Halmos , Xinhao Liu , Julian Gold , Benjamin J Raphael This is my paper · ORCID

classification cs.LGcs.AIstat.ML MSC 49Q2290C26

keywords low-rankoptimaltransportlatentcouplingfactorizationcoordinatemirrordescentfactorrelaxationSinkhornalgorithmGromov-Wassersteindistanceunbalancedspatialtranscriptomics

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

This paper claims that the low-rank optimal transport problem—finding a transport plan of rank at most $r$, with prescribed marginals, that minimizes a cost—can be reparameterized by a latent coupling (LC) factorization in which the plan is $P = Q\,\mathrm{diag}(1/g_Q)\,T\,\mathrm{diag}(1/g_R)\,R^T$, with $Q$ and $R$ matching the outer marginals and $T$ coupling two distinct inner marginals. Because the LC set surjects onto the set of rank-$r$ couplings, minimizing the cost over $(Q,R,T)$ is exactly the low-rank problem, not a proxy. On this parameterization the authors build FRLC, which alternates a factor-relaxation step (two independent semi-relaxed OT problems for $Q$ and $R$) with a balanced OT step for $T$, so each iteration is three Sinkhorn-type projections and the iterates stay feasible without Dykstra projections. They prove a non-asymptotic stationary convergence rate $O(1/N)$, and report lower primal costs than prior factored-coupling solvers on synthetic, graph-clustering, and spatial-transcriptomics tasks, while the latent coupling $T$ gives an interpretable cluster-level transport map.

What carries the argument

The machinery is the LC factorization $P = Q\,\mathrm{diag}(1/g_Q)\,T\,\mathrm{diag}(1/g_R)\,R^T$, whose key feature is two distinct inner marginals $g_Q$ and $g_R$ linked by a full coupling matrix $T$ rather than a shared diagonal $g$. The map from LC triples to couplings is surjective onto $\Pi_{a,b}(r)$, so the three-factor objective is equivalent to low-rank OT. Around this identity the paper builds a block-coordinate mirror-descent loop: a factor-relaxation step fixes $T$ and solves independent semi-relaxed OT problems for $Q$ and $R$, with a KL penalty pulling their inner marginals toward the previous values, and a latent-coupling step fixes $Q,R$ and solves a balanced OT problem for $T$. Feasibility follows automatically because the $(Q,R)$ step enforces the outer marginals and the $T$ step enforces the inner marginals, so the algorithm never needs Dykstra projections; the $\tau$ penalty supplies the smoothness constants used in the $O(1/N)$ convergence proof.

What would settle it

Run FRLC on a two-cluster cost matrix with a small penalty $\tau$ and monitor the smallest entries of $g_Q$ and $g_R$: Proposition E.5 requires them to stay above the fixed floor $\delta$ at every iteration. If some entry falls to zero while the iterates still converge, or if the convergence criterion $\Delta_k$ does not shrink like $1/N$ at the claimed smoothness constant $L$, then the uniform-lower-bound premise that carries the proof is violated.

Watch

Extended reading notes

Core claim

The paper's central claim is that the latent coupling factorization $P = Q\,\mathrm{diag}(1/g_Q)\,T\,\mathrm{diag}(1/g_R)\,R^T$, where $g_Q = Q^T1_n$ and $g_R = R^T1_m$ are two separate inner marginals and $T$ is any coupling between them, parameterizes the set of rank-$r$ couplings $\Pi_{a,b}(r)$ surjectively. Consequently the low-rank Wasserstein problem $\min_{P\in\Pi_{a,b}(r)}\langle C,P\rangle$ is equivalent to minimizing $L_{LC}(Q,R,T)=\langle C, Q\,\mathrm{diag}(1/g_Q)\,T\,\mathrm{diag}(1/g_R)\,R^T\rangle$ over admissible triples. The authors exploit this equivalence to design FRLC, which performs coordinate mirror descent on the blocks $(Q,R)$ and $T$: the $(Q,R)$ block update relaxes the inner marginal constraints, decoupling into two semi-relaxed OT problems, while the $T$ update is a balanced OT problem; together these updates keep every iterate feasible without Dykstra projections. Under a $\tau$-regularized inner-marginal penalty that enforces a uniform lower bound $\delta$ on the entries of $g_Q$ and $g_R$, the objective is component-wise smooth and FRLC attains non-asymptotic stationary convergence $\min_k \Delta_k \le 2D^2L^2/(N\alpha^2)$, i.e. $O(1/N)$.

Load-bearing premise

The convergence proof rests on assuming that a tunable penalty $\tau$ keeps every entry of the two inner marginals (the column sums of $Q$ and the column sums of $R$) bounded away from zero throughout all iterations; if that lower bound is not actually delivered, the smoothness lemma and the $O(1/N)$ rate do not follow.

Editorial extensions

If this is right

Because $LC_{a,b}(r)$ surjects onto $\Pi_{a,b}(r)$, any feasible rank-$r$ coupling has an LC representation, so minimizing $L_{LC}$ is exactly the low-rank OT problem and introduces no additional proxy error.
FRLC splits each iteration into two semi-relaxed OT problems and one balanced OT problem, all solved with Sinkhorn, and iterates remain in the constraint set without Dykstra projections.
With the $\tau$ penalty enforcing a uniform lower bound on inner-marginal entries, the FRLC objective is component-wise smooth and the algorithm attains $\min_k \Delta_k = O(1/N)$ in the stationarity criterion.
The same framework extends to Wasserstein, Gromov-Wasserstein, and fused Gromov-Wasserstein objectives under balanced, unbalanced, or semi-relaxed marginal constraints, with storage linear in the data size for fixed rank.
On synthetic mixtures, graph partitioning, and mouse-embryo spatial transcriptomics, FRLC reaches lower primal cost or better downstream alignment metrics than the factored-coupling solvers it compares with, while its non-diagonal latent coupling $T$ gives a cluster-level interpretation.

Reading between the lines

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

Editorial inference: because the LC parameterization is exactly equivalent to the rank-$r$ problem, the non-diagonal latent coupling $T$ is the structural novelty relative to diagonal factored-coupling solvers; a controlled comparison that diagonalizes FRLC's output would isolate how much of the empirical improvement comes from $T$ versus the coordinate split.
Editorial inference: the convergence guarantee depends on the $\tau$ penalty keeping inner marginals bounded away from zero, so a testable robustness criterion is to measure the empirical stationarity gap as $\tau$ is reduced on a fixed dataset; performance should degrade gracefully until the proof's regime ends.
Editorial inference: the two distinct inner marginals make the LC factorization a natural tool for comparing datasets with different numbers of latent clusters; the paper's non-square example suggests that the learned $T$ estimates a coarse-grained transition between clusters, which could be validated against the coarse-grained full-rank optimal plan when the Monge map is known.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 core algorithmic idea is sound and the paper deserves a serious referee. What's new: applying the LC factorization of Lin et al. to the primal low-rank OT problem with general costs, and a coordinate mirror descent scheme that decouples into three OT subproblems, avoiding Dykstra projections entirely. The structural advantage is real: the alternating updates keep iterates feasible by construction, and the extension to unbalanced and semi-relaxed settings follows naturally from the same scheme. The empirical work is broad — synthetic benchmarks, graph clustering, spatial transcriptomics — and the shipped code makes the comparisons reproducible. The parameterization surjectivity and the equivalence between the LC objective and the low-rank problem are correct, and the initialization trick (full-rank random via Sinkhorn) is a small but useful contribution.

The soft spot is the convergence proof. Proposition E.5 claims a uniform lower bound δ on the inner marginals g_Q and g_R, which is needed for the block-smoothness constants and hence for the O(1/N) rate in Proposition 3.4. The argument asserts that large τ and O~(m²/ε) Sinkhorn iterations force ||g^(k) − g^(k−1)|| below ε, and that telescoping gives the δ bound. That does not follow. The τ penalty pulls the inner marginal toward the previous iterate, but the semi-relaxed projection is still an OT solve whose output marginal can have entries driven arbitrarily close to zero by the linear cost, regardless of τ. Pham et al. bounds the solver's distance to the fixed point, not the gap between that fixed point and the target b. So the δ-bound is not established, and the non-asymptotic rate is unsupported. This is a genuine gap, but it is localized: the feasibility claim, the no-Dykstra advantage, and the empirical comparisons stand on their own. The paper even acknowledges the criterion is weak, which is honest but doesn't fix the proof.

Minor issue: the conclusion overstates the unbalanced FGW results slightly, since the gains there are smaller than in the Wasserstein case.

Bottom line: this is a worthwhile paper for the OT/ML audience. The convergence section needs a real fix — either a correct bound on the marginal gap, a weaker convergence statement, or an explicit caveat that the rate is empirical. With that, I'd support acceptance.

Referee Report

2 major / 4 minor

Summary. The paper introduces FRLC, a coordinate mirror-descent algorithm for low-rank optimal transport based on the latent-coupling (LC) factorization P = Q diag(1/g_Q) T diag(1/g_R) R^T, where T is a coupling between two distinct inner marginals g_Q and g_R. The main claims are that (i) the LC factorization parameterizes the rank-constrained coupling set Π_{a,b}(r) surjectively, so minimizing the LC objective is equivalent to the low-rank OT problem; (ii) FRLC decouples the optimization into three OT subproblems and remains feasible without Dykstra projections; (iii) FRLC converges with a non-asymptotic O(1/N) rate under a convergence criterion based on Ghadimi et al.; and (iv) FRLC extends to Wasserstein, Gromov-Wasserstein, and Fused Gromov-Wasserstein objectives with balanced, unbalanced, and semi-relaxed marginals. The paper supports these claims with a convergence analysis in Appendix E, an initialization analysis in Appendix F, and experiments on synthetic data, spatial transcriptomics, and graph partitioning.

Significance. If the claims are correct, the LC parameterization is a useful alternative to the factored couplings of Scetbon et al.: it decouples the low-rank OT problem into three OT subproblems, gives an interpretable latent coupling between two sets of barycenters, and naturally extends to unbalanced and semi-relaxed settings. The surjectivity argument for LCa,b(r) is sound and self-contained, the no-Dykstra feasibility structure is a genuine algorithmic advantage when implemented correctly, and the paper ships code and a broad experimental comparison. The improved low-rank approximation bound in Proposition E.7 is also a concrete contribution. However, two load-bearing points need work: the proof of the uniform lower-bound δ in Proposition E.5 does not establish the claimed marginal stabilization, and the pseudocode as printed contains swapped marginal conventions in the semi-relaxed projection and the Sinkhorn call, so the stated feasibility and convergence guarantees are not currently established for the algorithm as written.

major comments (2)

[Appendix E, Proposition E.5 and Proposition 3.4] The proof of Proposition E.5 does not establish the uniform lower bound δ on the inner marginals. The key assertion is that for sufficiently large τ and N = O~(m^2/ε) inner iterations one can guarantee ||g_R^(k) − g_R^(k−1)||_2 < ε = (1/N)(1/r − δ), and that telescoping these bounds yields g_{R,k,i} > δ for all i. However, the cited result of Pham et al. (2020) controls the distance between Sinkhorn iterates and the fixed point of the semi-relaxed projection for a fixed kernel; it does not control the gap between that fixed point and the previous target g_R^(k−1). In the semi-relaxed projection of Algorithm 2, the output marginal satisfies q_i = b_i^s (K^T u)_i^{1−s} with s = τ/(τ + γ^{−1}) < 1, so for any finite τ the transport cost can make (K^T u)_i arbitrarily large and drive q_i arbitrarily close to zero. The τ-regularization biases the marginal toward the previous iterate but does not, as proved here, enforce a uniform δ independent of C. Since the block-smoothness constants in Proposition E.5 are L_i = poly(||C||_F, n, m, r, δ), the non-asymptotic rate O(1/N) in Proposition 3.4 is unsupported. The authors should either prove the lower bound under explicit conditions on τ, γ, and C, or revise the convergence guarantee.
[Algorithms 1, 2, and 5] The pseudocode as printed does not implement the stated constrained updates, so the feasibility/no-Dykstra claim in Section 3.2 does not follow for the algorithm as written. In Algorithm 2, the update v ← b/K^T u makes the column sums of the returned diag(u)K diag(v) equal to b, i.e., the second marginal is the hard one. The correct semi-relaxed projection for equations (21)–(22), where the outer marginal Q1_r = a is hard and the inner marginal is soft, requires u ← a/(Kv) and v ← (b/K^T u)^{τ/(τ+γ^{−1})}; the printed updates are reversed, and Algorithm 7 is identical to Algorithm 2 despite being labeled as the opposite relaxation. Consequently, the calls in Algorithm 1 pass the marginals in the wrong order. Similarly, since T should be in Π_{gQ,gR} with row sums g_Q and column sums g_R, the call Sinkhorn(K_T, g_R, g_Q, δ) in Algorithms 1 and 4 swaps the two marginals, because Algorithm 5 returns row sums equal to its first argument. With these swaps, the iterates produced by the pseudocode do not satisfy P1_m = a and P^T1_n = b. The authors should correct the pseudocode and check that the released code matches the corrected version.

minor comments (4)

[Proposition 3.3] The displayed bound is typeset in an algebraically ambiguous way: D^2 L/N (α^2/2L) is not equal to 2D^2 L^2/(N α^2) as written; the intended expression appears to be D^2 L/(N α^2/(2L)). Please fix the notation.
[Proposition E.6] The proof contains an unresolved cross-reference: 'The proof of this for FRLC is given in ??' should refer explicitly to Proposition E.5.
[Algorithms 2 and 7] Algorithm 2 and Algorithm 7 are identical even though one is called 'right marginal relaxed' and the other 'left marginal relaxed'; the labels or the updates should be corrected.
[Throughout] There are several typos, including 'straightfoward' in Section 1 and 'feasability' near the end of Section 3.2; these should be corrected in a final pass.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found; the central derivation is independent, though Proposition E.5's delta-bound is an unproved correctness gap and the paper contains minor non-load-bearing self-citations.

full rationale

The claimed derivation chain is free of circular reduction. The LC parameterization is credited to Lin et al. (2021); the surjectivity of (Q,R,T) -> Q diag(1/g_Q) T diag(1/g_R) R^T onto Pi_{a,b}(r) is proved via the external Cohen & Rothblum (1993) factored-coupling theorem, not by assuming the conclusion. The equivalence of problem (8) and low-rank problem (6) therefore follows from a cited external mathematical fact, and the FRLC coordinate mirror descent is a new combination of standard MD/Sinkhorn blocks. No fitted parameter is renamed as a prediction: tau and gamma are hyperparameters of the algorithm, and the empirical benchmarks are against external methods and held-out marker genes. The self-citations (Halmos et al. 2024; Liu et al. 2023) appear only as background or as a biological motivation for the semi-relaxed alignment variant; no load-bearing theorem or uniqueness claim is imported from them. The notable weakness is Proposition E.5: the proof asserts that 'with sufficiently large tau and N = O~(m^2/epsilon) sub-iterations, one can guarantee ||g_R^(k)-g_R^(k-1)|| < epsilon = (1/N)(1/r-delta)' and cites Pham et al. (2020). That citation bounds the Sinkhorn solver's error to the fixed point of the regularized projection, not the gap between that fixed point and the previous target g^(k-1); the telescoping argument therefore does not establish the uniform lower bound delta on g_Q and g_R that the smoothness constants and the O(1/N) rate in Proposition 3.4 require. This is an unsupported proof step and a correctness risk, but it is not a case of the result being equivalent to its own inputs. Score 2 reflects only the presence of minor non-load-bearing self-citations; the central derivation itself is not circular.

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

The algorithm introduces no new physical or mathematical entities; the latent coupling T is from prior work. The free parameters are algorithm hyperparameters, and the key unproven premise is the tau-induced lower bound on inner marginals.

free parameters (4)

tau (KL penalty strength) = grid searched (30-100 on spatial transcriptomics, 75 in roots-of-unity)
Controls the soft constraint on inner marginals; the convergence analysis requires it to be sufficiently large to guarantee the delta lower bound, and the grid search shows sensitivity.
gamma (step size scale) = 90 in roots-of-unity, grid searched in some experiments
Global mirror descent step size; normalized per iteration by the gradient norm.
rank r = 5 to 200 depending on the experiment
Latent dimension of Q, R, and T; chosen by hand for each application.
delta (lower bound) = not specified (assumed in (0, 1/r))
Assumed lower bound on inner marginal entries in Proposition E.5; the paper claims it is guaranteed for large tau but does not derive the guarantee.

assumptions (4)

domain assumption The LC parameterization LCa,b(r) is surjective onto the set of rank-r couplings Pi_{a,b}(r).
Proved via the injection of factored couplings into LC with T = diag(g), relying on Cohen-Rothblum's factorization theorem.
standard math Sinkhorn for semi-relaxed and unbalanced OT converges at rate O~(m^2/epsilon) for the inner solver.
Used in Proposition E.5 to bound the inner marginal drift; the cited bound controls the solver's tolerance, not the gap between the relaxed optimal marginal and the target.
standard math Block descent lemma of Beck and Tetruashvili (2013)
Used to extend the non-asymptotic convergence criterion of Ghadimi et al. (2014) to coordinate mirror descent.
ad hoc to paper For sufficiently large tau, the relaxed inner marginal stays within a small neighborhood of the target g^(k-1).
Assumed to prove the delta lower bound in Proposition E.5; not derived from any cited result.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling." pith.science (2026). https://pith.science/paper/ZDRENGO3

@misc{pith2026241110555,
  author       = {Pith},
  title        = {Pith review of: Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZDRENGO3}},
  note         = {Machine review of arXiv:2411.10555}
}

abstract

Optimal transport (OT) is a general framework for finding a minimum-cost transport plan, or coupling, between probability distributions, and has many applications in machine learning. A key challenge in applying OT to massive datasets is the quadratic scaling of the coupling matrix with the size of the dataset. [Forrow et al. 2019] introduced a factored coupling for the k-Wasserstein barycenter problem, which [Scetbon et al. 2021] adapted to solve the primal low-rank OT problem. We derive an alternative parameterization of the low-rank problem based on the $\textit{latent coupling}$ (LC) factorization previously introduced by [Lin et al. 2021] generalizing [Forrow et al. 2019]. The LC factorization has multiple advantages for low-rank OT including decoupling the problem into three OT problems and greater flexibility and interpretability. We leverage these advantages to derive a new algorithm $\textit{Factor Relaxation with Latent Coupling}$ (FRLC), which uses $\textit{coordinate}$ mirror descent to compute the LC factorization. FRLC handles multiple OT objectives (Wasserstein, Gromov-Wasserstein, Fused Gromov-Wasserstein), and marginal constraints (balanced, unbalanced, and semi-relaxed) with linear space complexity. We provide theoretical results on FRLC, and demonstrate superior performance on diverse applications -- including graph clustering and spatial transcriptomics -- while demonstrating its interpretability.

Figures

Figures reproduced from arXiv: 2411.10555 by the authors.

**Figure 1.** (Left) The LC factorization P = Qdiag(1/gQ)T diag(1/gR)RT of coupling matrix P with outer marginals a, b, inner marginals gQ, gR, factors Q, R, and latent coupling T . (Right) Full-rank coupling matrix P . this factorization is the presence of a coupling matrix T linking two distinct inner marginals. For simplicity we describe this factorization using an r-dimensional latent space, but we also extend to non-square m… view at source ↗

**Figure 2.** (a) Simulated dataset containing points from two moons (orange) and eight Gaussians [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** LC-projections of couplings of Gaussians centered on the 5 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (9 more)

**Figure 4.** Figure 4: (a) Brain marker gene Tubb2b expression and FRLC prediction. (b) Comparison of the low-rank unbalanced (LOT-U) algorithm of Scetbon et al. (2023) and FRLC on aligning spatial transcriptomics data. Bold indicates top performing method for each metric on each objective. …

**Figure 5.** Figure 5: Transport cost ⟨C, P ⟩F against number of iterations for FRLC with rank 200 on the synthetic dataset of two moons and eight Gaussians. Smooth convergence is observed for both rank-2 and full-rank random initialization. K Additional Simulations We tested on two addition…

**Figure 6.** Figure 6: Plot of the two simulated mixtures of Gaussians in 2D, following the same parameters as [PITH_FULL_IMAGE:figures/full_fig_p042_6.png]

**Figure 7.** Figure 7: Transport cost ⟨C, P ⟩F achieved by LOT Scetbon et al. (2021) and FRLC across different ranks and different initializations on the Wasserstein problem on the synthetic dataset of two mixtures of Gaussians in 2D. 42 [PITH_FULL_IMAGE:figures/full_fig_p042_7.png]

**Figure 8.** Figure 8: FRLC achieves lower primal cost ⟨C, P ⟩F for P ∈ Πa,b than Scetbon et al. (2021) on a spatial-transcriptomics dataset of mouse embryonic development Chen et al. (2022). FRLC demonstrates a more robust trend of improved performance with higher rank. η = 10−6 . SpecGWL C…

**Figure 9.** Figure 9: Visualization of the E11.5 and E12.5 mouse embryos, with each cell colored by the cell [PITH_FULL_IMAGE:figures/full_fig_p047_9.png]

**Figure 10.** Figure 10: Ground truth and the predicted cell type classification of the E12.5 embryo. [PITH_FULL_IMAGE:figures/full_fig_p051_10.png]

**Figure 11.** Figure 11: (a) LC-projection barycenters aligned with FRLC latent-coupling [PITH_FULL_IMAGE:figures/full_fig_p052_11.png]

**Figure 12.** Figure 12: As discussed in A.1, one may recover the factorization of Forrow et al. (2019) as a sub-case [PITH_FULL_IMAGE:figures/full_fig_p053_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 45 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

and Woodruff, D

Bakshi, A. and Woodruff, D. Sublinear T ime L ow- R ank A pproximation of D istance M atrices. Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[3]

G., Duflo, E., and Jackson, M

Banerjee, A., Chandrasekhar, A. G., Duflo, E., and Jackson, M. O. The D iffusion of M icrofinance. Science, 341 0 (6144): 0 1236498, 2013

work page 2013
[4]

Bauschke, H. H. and Lewis, A. S. Dykstras algorithm with B regman projections: A convergence proof. Optimization, 48 0 (4): 0 409–427, January 2000. ISSN 1029-4945. doi:10.1080/02331930008844513. URL http://dx.doi.org/10.1080/02331930008844513

doi:10.1080/02331930008844513
[5]

and Tetruashvili, L

Beck, A. and Tetruashvili, L. On the C onvergence of B lock C oordinate D escent T ype M ethods. SIAM J. Optim., 23: 0 2037--2060, 2013. URL https://api.semanticscholar.org/CorpusID:6866704

work page 2013
[6]

Iterative B regman P rojections for R egularized T ransportation P roblems

Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. Iterative B regman P rojections for R egularized T ransportation P roblems. SIAM Journal on Scientific Computing, 37 0 (2): 0 A1111–A1138, January 2015. ISSN 1095-7197. doi:10.1137/141000439. URL http://dx.doi.org/10.1137/141000439

doi:10.1137/141000439 2015
[7]

Bregman, L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7 0 (3): 0 200--217, 1967

work page 1967
[8]

G., Gut, G., del Castillo, J

Bunne, C., Stark, S. G., Gut, G., del Castillo, J. S., Levesque, M., Lehmann, K.-V., Pelkmans, L., Krause, A., and R \"a tsch, G. Learning single-cell perturbation responses using neural optimal transport. Nature Methods, 20 0 (11): 0 1759--1768, September 2023. ISSN 1548-7105. doi:10.1038/s41592-023-01969-x. URL http://dx.doi.org/10.1038/s41592-023-01969-x

doi:10.1038/s41592-023-01969-x 2023

Show all 58 references

[9]

Fast A lgorithms for a N ew R elaxation of O ptimal T ransport

Charikar, M., Chen, B., R \'e , C., and Waingarten, E. Fast A lgorithms for a N ew R elaxation of O ptimal T ransport. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp.\ 483...

2023
[10]

Spatiotemporal transcriptomic atlas of mouse organogenesis using DNA nanoball-patterned arrays

Chen, A., Liao, S., Cheng, M., Ma, K., Wu, L., Lai, Y., Qiu, X., Yang, J., Xu, J., Hao, S., et al. Spatiotemporal transcriptomic atlas of mouse organogenesis using DNA nanoball-patterned arrays. Cell, 185 0 (10): 0 1777--1792, 2022

2022
[11]

and Price, E

Chen, X. and Price, E. Condition number-free query and active learning of linear families. 2017

2017
[12]

Unbalanced O ptimal T ransport: D ynamic and K antorovich F ormulations

Chizat, L., Peyré, G., Schmitzer, B., and Vialard, F.-X. Unbalanced O ptimal T ransport: D ynamic and K antorovich F ormulations. Journal of Functional Analysis, 274 0 (11): 0 3090–3123, June 2018. ISSN 0022-1236. doi:10.1016/j.jfa.2018.03.008. URL http://dx.doi.org/10.1016/j....

2018 doi
[13]

and Needham, T

Chowdhury, S. and Needham, T. Generalized S pectral C lustering via G romov- W asserstein L earning. In International Conference on Artificial Intelligence and Statistics, pp.\ 712--720. PMLR, 2021

2021
[14]

Laplacians and the C heeger I nequality for D irected G raphs

Chung, F. Laplacians and the C heeger I nequality for D irected G raphs. Annals of Combinatorics, 9: 0 1--19, 2005

2005
[15]

Cohen, J. E. and Rothblum, U. G. Nonnegative R anks, D ecompositions, and F actorizations of N onnegative M atrices. Linear Algebra and its Applications, 190: 0 149--168, 1993

1993
[16]

Domain adaptation with regularized optimal transport

Courty, N., Flamary, R., and Tuia, D. Domain adaptation with regularized optimal transport. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part I 14, pp.\ 274--289. Springer, 2014

2014
[17]

Sinkhorn D istances: L ightspeed C omputation of O ptimal T ransport

Cuturi, M. Sinkhorn D istances: L ightspeed C omputation of O ptimal T ransport. Advances in neural information processing systems, 26, 2013 a

2013
[18]

Sinkhorn distances: Lightspeed computation of optimal transport

Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, pp.\ 2292--2300, 2013 b . URL https://proceedings.neurips.cc/paper/2013/hash/af21d0c97db2e27e13572cbf59eb343d-Abstract.html

2013
[19]

Optimal T ransport T ools ( OTT ): A JAX T oolbox for all things W asserstein

Cuturi, M., Meng-Papaxanthos, L., Tian, Y., Bunne, C., Davis, G., and Teboul, O. Optimal T ransport T ools ( OTT ): A JAX T oolbox for all things W asserstein. arXiv preprint arXiv:2201.12324, 2022

2022 arXiv
[20]

Dang, C. D. and Lan, G. Stochastic B lock M irror D escent M ethods for N onsmooth and S tochastic O ptimization. SIAM J. Optim., 25 0 (2): 0 856--881, January 2015

2015
[21]

Partial unbalanced feature transport for cross-modality cardiac image segmentation

Dong, S., Pan, Z., Fu, Y., Xu, D., Shi, K., Yang, Q., Shi, Y., and Zhuo, C. Partial unbalanced feature transport for cross-modality cardiac image segmentation. IEEE Transactions on Medical Imaging, 2023

2023
[22]

Dykstra, R. L. An A lgorithm for R estricted L east S quares R egression. Journal of the American Statistical Association, 78 0 (384): 0 837–842, December 1983. ISSN 1537-274X. doi:10.1080/01621459.1983.10477029. URL http://dx.doi.org/10.1080/01621459.1983.10477029

1983
[23]

Statistical O ptimal T ransport via F actored C ouplings

Forrow, A., H\" u tter, J.-C., Nitzan, M., Rigollet, P., Schiebinger, G., and Weed, J. Statistical O ptimal T ransport via F actored C ouplings. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and S...

2019
[24]

Fast M onte- C arlo A lgorithms for F inding L ow-rank A pproximations

Frieze, A., Kannan, R., and Vempala, S. Fast M onte- C arlo A lgorithms for F inding L ow-rank A pproximations. J. ACM, 51 0 (6): 0 1025–1041, nov 2004. ISSN 0004-5411. doi:10.1145/1039488.1039494. URL https://doi.org/10.1145/1039488.1039494

2004
[25]

Frogner, C., Zhang, C., Mobahi, H., Araya, M., and Poggio, T. A. Learning with a W asserstein L oss. Advances in neural information processing systems, 28, 2015

2015
[26]

A mathematical perspective on T ransformers

Geshkovski, B., Letrouit, C., Polyanskiy, Y., and Rigollet, P. A mathematical perspective on T ransformers. arXiv preprint arXiv:2312.10794, 2023

2023 arXiv
[27]

Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

Ghadimi, S., Lan, G., and Zhang, H. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155 0 (1–2): 0 267–305, December 2014. ISSN 1436-4646. doi:10.1007/s10107-014-0846-1. URL http://dx.doi.org/10.1007/s10107...

2014 doi
[28]

Halmos, P., Liu, X., Gold, J., Chen, F., Ding, L., and Raphael, B. J. De ST - OT : Alignment of S patiotemporal T ranscriptomics D ata. In International Conference on Research in Computational Molecular Biology, pp.\ 434--437. Springer, 2024

2024
[29]

Indyk, P., Vakilian, A., Wagner, T., and Woodruff, D. P. Sample-optimal low-rank approximation of distance matrices. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp...

2019
[30]

On the T ranslocation of M asses: Doklady akademii nauk ussr

Kantorovich, L. On the T ranslocation of M asses: Doklady akademii nauk ussr. 1942

1942
[31]

Mapping cells through time and space with moscot

Klein, D., Palla, G., Lange, M., Klein, M., Piran, Z., Gander, M., Meng-Papaxanthos, L., Sterr, M., Bastidas-Ponce, A., Tarquis-Medina, M., et al. Mapping cells through time and space with moscot. bioRxiv, pp.\ 2023--05, 2023

2023
[32]

Lin, C.-H., Azabou, M., and Dyer, E. L. Making transport more robust and interpretable by moving data through a small number of anchor points. Proceedings of machine learning research, 139: 0 6631, 2021

2021
[33]

Approximating optimal transport via low-rank and sparse factorization

Liu, W., Zhang, C., Zheng, N., and Qian, H. Approximating optimal transport via low-rank and sparse factorization. CoRR, abs/2111.06546, 2021. URL https://arxiv.org/abs/2111.06546

2021 arXiv
[34]

Liu, X., Zeira, R., and Raphael, B. J. Partial alignment of multislice spatially resolved transcriptomics data. Genome Research, 33 0 (7): 0 1124--1132, 2023

2023
[35]

On the use of G romov- H ausdorff D istances for S hape C omparison

M \'e moli, F. On the use of G romov- H ausdorff D istances for S hape C omparison. 2007

2007
[36]

Gromov-- W asserstein D istances and the M etric A pproach to O bject M atching

M \'e moli, F. Gromov-- W asserstein D istances and the M etric A pproach to O bject M atching. Foundations of computational mathematics, 11: 0 417--487, 2011

2011
[37]

Efficiency of C oordinate D escent M ethods on H uge- S cale O ptimization P roblems

Nesterov, Y. Efficiency of C oordinate D escent M ethods on H uge- S cale O ptimization P roblems. SIAM Journal on Optimization, 22 0 (2): 0 341--362, 2012

2012
[38]

Orlin, J. B. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78 0 (2): 0 109--129, Aug 1997. ISSN 1436-4646. doi:10.1007/BF02614365. URL https://link.springer.com/content/pdf/10.1007/BF02614365.pdf

1997 doi
[39]

Pham, K., Le, K., Ho, N., Pham, T., and Bui, H. H. On U nbalanced O ptimal T ransport: An A nalysis of S inkhorn A lgorithm. In International Conference on Machine Learning, 2020. URL https://api.semanticscholar.org/CorpusID:211068892

2020
[40]

E., Ablin, P., Blondel, M., and Peyr\'e, G

Sander, M. E., Ablin, P., Blondel, M., and Peyr\'e, G. Sinkformers: Transformers with D oubly S tochastic A ttention. In Camps-Valls, G., Ruiz, F. J. R., and Valera, I. (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 1...

2022
[41]

and Cuturi, M

Scetbon, M. and Cuturi, M. Low-rank O ptimal T ransport: A pproximation, S tatistics and D ebiasing. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=4btNeXKFAQ

2022
[42]

Low- R ank S inkhorn F actorization

Scetbon, M., Cuturi, M., and Peyr\' e , G. Low- R ank S inkhorn F actorization. In International Conference on Machine Learning, 2021. URL https://api.semanticscholar.org/CorpusID:232147563

2021
[43]

Linear-time G romov W asserstein D istances using L ow R ank C ouplings and C osts

Scetbon, M., Peyr \'e , G., and Cuturi, M. Linear-time G romov W asserstein D istances using L ow R ank C ouplings and C osts. In International Conference on Machine Learning, pp.\ 19347--19365. PMLR, 2022

2022
[44]

Unbalanced L ow-rank O ptimal T ransport S olvers, 2023

Scetbon, M., Klein, M., Palla, G., and Cuturi, M. Unbalanced L ow-rank O ptimal T ransport S olvers, 2023

2023
[45]

Optimal- T ransport A nalysis of S ingle- C ell G ene E xpression I dentifies D evelopmental T rajectories in R eprogramming

Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., et al. Optimal- T ransport A nalysis of S ingle- C ell G ene E xpression I dentifies D evelopmental T rajectories in R eprogramming. Cell, 176 0 (4): 0 928-...

2019
[46]

Convolutional W asserstein D istances: Efficient O ptimal T ransportation on G eometric D omains

Solomon, J., De Goes, F., Peyr \'e , G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., and Guibas, L. Convolutional W asserstein D istances: Efficient O ptimal T ransportation on G eometric D omains. ACM Transactions on Graphics (ToG), 34 0 (4): 0 1--11, 2015

2015
[47]

L., Salm \'e n, F., Vickovic, S., Lundmark, A., Navarro, J

St hl, P. L., Salm \'e n, F., Vickovic, S., Lundmark, A., Navarro, J. F., Magnusson, J., Giacomello, S., Asp, M., Westholm, J. O., Huss, M., et al. Visualization and analysis of gene expression in tissue sections by spatial transcriptomics. Science, 353 0 (6294): 0 78--82, 2016

2016
[48]

Tarjan, R. E. Dynamic trees as search trees via E uler tours, applied to the network simplex algorithm. Mathematical Programming, 78 0 (2): 0 169--177, Aug 1997. ISSN 1436-4646. doi:10.1007/BF02614369. URL https://link.springer.com/content/pdf/10.1007/BF02614369.pdf

1997 doi
[49]

Sparse S inkhorn A ttention

Tay, Y., Bahri, D., Yang, L., Metzler, D., and Juan, D.-C. Sparse S inkhorn A ttention. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp.\ 9438--9447. PMLR, 13--...

2020
[50]

Improving and generalizing flow-based generative models with minibatch optimal transport

Tong, A., Malkin, N., Huguet, G., Zhang, Y., Rector-Brooks, J., Fatras, K., Wolf, G., and Bengio, Y. Improving and generalizing flow-based generative models with minibatch optimal transport. In ICML Workshop on New Frontiers in Learning, Control, and Dynamical Systems, 2023

2023
[51]

Fused G romov- W asserstein distance for structured objects

Vayer, T., Chapel, L., Flamary, R., Tavenard, R., and Courty, N. Fused G romov- W asserstein distance for structured objects. Algorithms, 13 0 (9): 0 212, August 2020. ISSN 1999-4893. doi:10.3390/a13090212. URL http://dx.doi.org/10.3390/a13090212

2020 doi
[52]

Semi-relaxed G romov- W asserstein divergence and applications on graphs

Vincent-Cuaz, C., Flamary, R., Corneli, M., Vayer, T., and Courty, N. Semi-relaxed G romov- W asserstein divergence and applications on graphs. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=RShaMexjc-x

2022
[53]

A., Angerer, P., and Theis, F

Wolf, F. A., Angerer, P., and Theis, F. J. SCANPY : large-scale single-cell gene expression data analysis. Genome biology, 19: 0 1--5, 2018

2018
[54]

Xu, H., Luo, D., Zha, H., and Duke, L. C. Gromov- W asserstein L earning for G raph M atching and N ode E mbedding. In International conference on machine learning, pp.\ 6932--6941. PMLR, 2019

2019
[55]

and Leskovec, J

Yang, J. and Leskovec, J. Defining and E valuating N etwork C ommunities based on G round-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp.\ 1--8, 2012

2012
[56]

D., Damodaran, K., Venkatachalapathy, S., Soylemezoglu, A

Yang, K. D., Damodaran, K., Venkatachalapathy, S., Soylemezoglu, A. C., Shivashankar, G., and Uhler, C. Predicting cell lineages using autoencoders and optimal transport. PLoS computational biology, 16 0 (4): 0 e1007828, 2020

2020
[57]

R., Leskovec, J., and Gleich, D

Yin, H., Benson, A. R., Leskovec, J., and Gleich, D. F. Local H igher- O rder G raph C lustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp.\ 555--564, 2017

2017
[58]

Zeira, R., Land, M., Strzalkowski, A., and Raphael, B. J. Alignment and integration of spatial transcriptomics data. Nature Methods, 19 0 (5): 0 567--575, 2022

2022

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

and Woodruff, D

Bakshi, A. and Woodruff, D. Sublinear T ime L ow- R ank A pproximation of D istance M atrices. Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[3] [3]

G., Duflo, E., and Jackson, M

Banerjee, A., Chandrasekhar, A. G., Duflo, E., and Jackson, M. O. The D iffusion of M icrofinance. Science, 341 0 (6144): 0 1236498, 2013

work page 2013

[4] [4]

Bauschke, H. H. and Lewis, A. S. Dykstras algorithm with B regman projections: A convergence proof. Optimization, 48 0 (4): 0 409–427, January 2000. ISSN 1029-4945. doi:10.1080/02331930008844513. URL http://dx.doi.org/10.1080/02331930008844513

doi:10.1080/02331930008844513

[5] [5]

and Tetruashvili, L

Beck, A. and Tetruashvili, L. On the C onvergence of B lock C oordinate D escent T ype M ethods. SIAM J. Optim., 23: 0 2037--2060, 2013. URL https://api.semanticscholar.org/CorpusID:6866704

work page 2013

[6] [6]

Iterative B regman P rojections for R egularized T ransportation P roblems

Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. Iterative B regman P rojections for R egularized T ransportation P roblems. SIAM Journal on Scientific Computing, 37 0 (2): 0 A1111–A1138, January 2015. ISSN 1095-7197. doi:10.1137/141000439. URL http://dx.doi.org/10.1137/141000439

doi:10.1137/141000439 2015

[7] [7]

Bregman, L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7 0 (3): 0 200--217, 1967

work page 1967

[8] [8]

G., Gut, G., del Castillo, J

Bunne, C., Stark, S. G., Gut, G., del Castillo, J. S., Levesque, M., Lehmann, K.-V., Pelkmans, L., Krause, A., and R \"a tsch, G. Learning single-cell perturbation responses using neural optimal transport. Nature Methods, 20 0 (11): 0 1759--1768, September 2023. ISSN 1548-7105. doi:10.1038/s41592-023-01969-x. URL http://dx.doi.org/10.1038/s41592-023-01969-x

doi:10.1038/s41592-023-01969-x 2023