Research Radar — 2026-11-04

Methodology Review: Entropic optimal transport: matching distributions by scaling rows and columns

English · About 10 minutes

Evidence: primary mathematical and computational papers. Worked examples are independently derived illustrations; proposed omics transfers are speculative, not validated applications.

The intuition

Suppose two collections contain the same total amount of material, but their contents occupy different positions in a feature space. Comparing bin counts independently ignores whether a discrepancy is nearby or far away. Optimal transport instead asks for a shipping plan: how much of each source location should supply each destination, given a cost for each possible pairing? The plan must respect both sets of totals. Those constraints are the crucial difference from simply choosing the nearest destination for every source. [R2]

Entropy regularization makes this constrained matching problem smoother by rewarding spread-out plans. Sinkhorn scaling then alternates between repairing the source totals and repairing the destination totals. Each repair is simple, although repairing one side generally disturbs the other. The method is not a proof that the resulting pairings happened in the world. Think of it as an explicitly chosen rule for distributing correspondence, with a controllable preference for diffuse answers. [R1]

A small worked example

Here is a complete two-location exercise, constructed for this review rather than taken from a dataset. Both distributions place half their mass at each of two locations. Staying at the corresponding location costs zero; crossing costs one. Every feasible symmetric plan therefore has diagonal entries equal to a number called t and off-diagonal entries equal to one half minus t. The unregularized minimum puts one half on each diagonal and zero elsewhere. Its shipping cost is zero, which makes the effect of regularization especially easy to see.

Choose the regularization parameter \(\varepsilon=1/\log 3\), where log is the natural logarithm. The positive kernel has diagonal entries one and off-diagonal entries one third. Starting the column scaling vector at two ones, each row has total four thirds. Multiplying both rows by three eighths produces diagonal entries three eighths and off-diagonal entries one eighth. Each column now also sums to one half, so the column correction is one and this example has already converged. Its transport cost is one quarter: two off-diagonal masses of one eighth each pay a cost of one.

Check the answer without trusting an iteration. The scalar objective along the feasible plans is \(F(t)=1-2t+2\varepsilon[t\log t+(1/2-t)\log(1/2-t)-1/2]\). Its derivative is \(F^{\prime}(t)=-2+2\varepsilon\log[t/(1/2-t)]\). Setting that derivative to zero gives a diagonal-to-off-diagonal ratio of three and hence \(t=3/8\). The second derivative is positive in the interior, so this stationary point is the unique minimum. This arithmetic illustrates why regularization produces crossings even when the distributions are identical; the crossings are not evidence of movement.

Try changing the crossing cost from one to two while leaving the regularization parameter unchanged. The kernel ratio becomes nine rather than three, so each diagonal mass becomes nine twentieths and each off-diagonal mass one twentieth. Doubling all costs and the regularization parameter together instead leaves the plan unchanged. This is a useful unit check: the parameter has meaning relative to the scale of the costs, not as a universal decimal chosen independently of preprocessing.

The necessary mathematics

Let \(a_i\) and \(b_j\) be positive source and destination masses, each collection summing to one. Indices i and j enumerate their locations. Let \(C_{ij}\) be the finite cost of pairing them, and \(P_{ij}\) the nonnegative amount assigned to that pair. For a positive parameter epsilon, the entropic objective is:

The constraints are \(\sum_j P_{ij}=a_i\) and \(\sum_i P_{ij}=b_j\). At zero mass, the entropy contribution is defined by continuity. This is a regularized objective, not automatically a metric. [R2]

Define \(K_{ij}=\exp(-C_{ij}/\varepsilon)\). The optimal plan has the form \(P_{ij}=u_iK_{ij}v_j\), where u and v are positive scaling vectors. Start v positive, then update \(u_i=\frac{a_i}{\sum_j K_{ij}v_j}\) followed by \(v_j=\frac{b_j}{\sum_i K_{ij}u_i}\), using the newly computed u. These are componentwise divisions; the sums are matrix-vector products. Stop only after checking both marginal discrepancies, not merely that the latest columns look correct. [R1]

Another interpretation is alternating projections in relative-entropy geometry. The row and column constraints are individually easy to enforce. Their intersection is the feasible set we actually want. Benamou and colleagues connect this procedure to more general constrained transport problems, while distinguishing equality constraints from cases with inequalities. This matters when modifying an algorithm: adding a capacity limit and retaining the same naive alternation is not automatically a correct solver for the changed problem. [R4]

Assumptions and failure modes

The simple formulas assume finite costs and positive retained masses. Remove empty bins deliberately rather than dividing by zero. Very small regularization can make kernel entries underflow to zero and slow convergence; log-domain implementations address numerical stability. Dense pairwise costs still require substantial memory. A fast matrix-vector loop does not remove the need to store or otherwise evaluate all relevant costs. These are numerical constraints, separate from whether the chosen geometry answers a scientific question. [R2]

There is also a reporting trap. The transport cost evaluated at a regularized plan, the complete entropy-penalized objective, and a debiased Sinkhorn divergence are different quantities. Feydy and colleagues study a correction that subtracts self-comparison terms, with theoretical guarantees under their assumptions. Do not transfer those guarantees indiscriminately to every quantity called a Sinkhorn distance. Our identical-distribution example deliberately has positive shipping cost; that alone shows why naming the reported number matters. [R3]

For an analysis checklist, ask what one unit of mass represents. Equal weighting of individual observations gives a different question from equal weighting of donors or specimens. Next ask what makes a pairing cheap: shared technical artifacts can create attractive but scientifically misleading matches. Finally ask whether unequal abundance is signal or nuisance. Normalizing both collections to total one removes total abundance information before the optimization begins. No convergence tolerance can recover information deliberately removed upstream.

Verified applications

Cuturi reports a computational and classification experiment on MNIST handwritten digits, using image histograms to compare the regularized approach with classical transport. This is an established machine-learning demonstration, not a biomedical validation or a claim that its reported speed advantage transfers unchanged to current hardware and software. The original conference paper is the main reading because it makes the computational mechanism visible without requiring an entire survey. [R1]

Benamou and colleagues give numerical examples involving transport barycenters and tomographic reconstruction, among other constrained problems. These establish broader uses of the projection framework beyond a single pair of histograms. Feydy and colleagues study large-scale differentiable distribution comparisons and the properties of their debiased divergence. None of these inspected papers is presented here as validation of a particular single-cell integration pipeline. [R4] [R3]

Possible transfers — speculative

A speculative omics exercise would compare two distributions of a predefined low-dimensional measurement score while keeping specimen identities intact. Begin with artificial distributions whose shifts are known, vary the cost scaling and regularization, and inspect the complete plan rather than only its total cost. Then compare results with a simpler histogram summary. This is a proposed diagnostic exercise, not a validated biological workflow, and it should not be interpreted as reconstruction of cell ancestry.

A second speculative use is teaching alignment uncertainty: hold the observed distributions fixed, change plausible cost representations, and show which correspondences survive. The purpose would be to reveal dependence on modeling choices rather than select the most visually convincing alignment. Before applying it to real experiments, define a held-out evaluation criterion and state what independent evidence could contradict the proposed correspondences. Distributional matching alone cannot establish a causal transition.

What to try and what to read next

Reproduce the two-by-two calculation first. Print row totals, column totals, shipping cost and the entropy term separately. Increase regularization until the plan becomes visibly diffuse, then lower it and watch numerical behavior. The practical lesson is that an algorithm can satisfy every constraint and still answer the wrong scientific question if the cost or mass definition was poorly chosen. Read the main paper for the scaling idea, the survey for implementation cautions, the divergence paper for interpretation, and the projection paper before adding new constraints.

Reading list

• [R1] Primary reading: Sinkhorn Distances: Lightspeed Computation of Optimal Transport. Marco Cuturi (2013). Main reading: focus on the matrix-scaling derivation and its computational experiment. Conference publication: 2013; author preprint first posted 2013-06-04, arXiv:1306.0895.

• [R2] Related reading: Computational Optimal Transport: With Applications to Data Science. Gabriel Peyré and Marco Cuturi (2019). Background and numerical cautions: chapter 4. First preprint 2018-03-01; journal 2019; corrected author version v4 dated 2020-03-18. These are one reading.

• [R3] Related reading: Interpolating between Optimal Transport and MMD using Sinkhorn Divergences. Jean Feydy, Thibault Séjourné, François-Xavier Vialard, Shun-ichi Amari, Alain Trouvé and Gabriel Peyré (2019). Correction and interpretation: distinguish a regularized transport objective from the debiased Sinkhorn divergence. AISTATS proceedings April 2019; preprint first posted 2018-10-18.

• [R4] Related reading: Iterative Bregman Projections for Regularized Transportation Problems. Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna and Gabriel Peyré (2015). Extension: why alternating simple projections work for equality constraints and why inequality constraints need more care. Journal 2015; preprint first posted 2014-12-16.