Entropic Regularization: Sinkhorn Algorithm

Entropic regularization makes optimal transport smooth, strictly convex and scalable. This chapter first explains the discrete KL-regularized problem, derives Sinkhorn’s alternating matrix scaling algorithm, and then rewrites the same construction as a relative-entropy projection problem. It then records the general continuous formulation, explains the path-space Schrodinger problem behind the static coupling formulation, develops the dual soft-transform picture, and presents the main convex regularization variants and the debiased Sinkhorn divergence.

The presentation connects the older matrix-scaling literature Sinkhorn, 1964Sinkhorn & Knopp, 1967Sinkhorn, 1967 with modern entropic OT Cuturi, 2013Peyré & Cuturi, 2019.

from pathlib import Path
import sys

from IPython.display import Image as DisplayImage
from IPython.display import display

here = Path.cwd()
myst_dir = None
for candidate in [here, here.parent, here / "myst", here.parent / "myst", here.parent.parent / "myst"]:
    if (candidate / "ot4ml_web.py").exists():
        myst_dir = candidate.resolve()
        sys.path.insert(0, str(myst_dir))
        break

if myst_dir is None:
    raise RuntimeError("Could not locate myst/ot4ml_web.py")

repo_root = myst_dir.parent
thumbnails = repo_root / "notebooks-figures" / "thumbnails"

def show_book_figure(name, width=760):
    display(DisplayImage(filename=str(thumbnails / f"{name}.png"), width=width))

Entropic Regularization for Discrete Measures¶

Entropy turns a possibly non-unique linear program into a unique smooth problem. The price is bias, but the reward is differentiability and fast scaling algorithms.

Using this entropy as a regularizing function gives the approximate transport value

\mathcal{L}_{C}^{\epsilon}(a,b) \eqdef \min_{P\in\mathbf{U}(a,b)} \langle P,C\rangle - \epsilon H(P).

(2)

Equivalently, the regularizer is $\epsilon\sum_{i,j}P_{i,j}\log P_{i,j}$ . It penalizes concentrated couplings and makes the objective strictly convex on the relative interior of the transport polytope.

Smoothing Effect¶

The entropy acts as a barrier for positivity and makes $\mathcal{L}_{C}^{\epsilon}(a,b)$ smooth in $a$ , $b$ , and $C$ as long as these variables stay in the relative interior. As $\epsilon\to+\infty$ , the minimizer converges to the independent coupling $a\otimes b$ ; as $\epsilon\to0$ , it approaches the optimal face of the original transport linear program.

Entropic regularization and slack barriers. Large $\epsilon$ selects an interior reference point, while small $\epsilon$ moves the minimizer toward a low-cost face of the transport polytope. The second row gives the analogous entropy-on-slacks picture for a generic linear program.

Entropy Barriers Versus Generic LP Barriers¶

For a generic linear program $\min_z \ell^\top z$ with constraints $Az\le b$ , one can introduce positive slacks $s=b-Az$ and penalize them by an entropy. This is a useful analogy, but it is not the standard self-concordant interior-point barrier. The canonical barrier is the Burg, or reverse-KL, barrier $-\sum_i\log s_i$ , which leads to Newton systems.

Optimal transport is special because entropy is placed on the entries of $P$ , while the constraints are only row and column marginals. This separable structure turns Bregman projections into diagonal rescalings, giving the Sinkhorn iterations.

Sinkhorn’s Algorithm¶

Sinkhorn’s algorithm is alternating normalization of rows and columns. The key point is that the optimizer of the entropic problem has a multiplicative scaling form.

In matrix notation, $P=\operatorname{diag}(u)K\operatorname{diag}(v)$ . The marginal constraints become

u\odot(Kv)=a, \qquad v\odot(K^\top u)=b.

(7)

Solving each equation in turn gives Sinkhorn’s algorithm:

u^{(\ell+1)} = \frac{a}{Kv^{(\ell)}}, \qquad v^{(\ell+1)} = \frac{b}{K^\top u^{(\ell+1)}}.

(8)

The division is entrywise. The scaling vectors are not unique: multiplying $u$ by $\lambda>0$ and $v$ by $1/\lambda$ leaves $P$ unchanged.

Marginal constraints during Sinkhorn scaling. Row normalizations align the red source marginal and leave a blue defect; column normalizations align the blue target marginal and leave a red defect.

The interactive demo exposes the alternating row/column normalization directly. Change the half-step count to see the current coupling acquire one marginal, lose the other, and then converge toward both.

Interactive panel. Use the iteration, regularization, and mass controls to watch Sinkhorn row and column scalings enforce the marginals.

Dense Sinkhorn scaling for one-dimensional Gaussian-mixture marginals. The violet side curves are the current row and column sums; the red and blue curves are the prescribed marginals.

After convergence, the regularization strength controls how much of the Gibbs kernel remains visible in the optimal plan. Small $\epsilon$ produces a concentrated transport band, while larger $\epsilon$ spreads the same marginals into a smoother coupling.

Final Sinkhorn couplings for the same one-dimensional marginals and four regularization strengths. Decreasing $\epsilon$ sharpens the plan toward an optimal-transport graph; increasing $\epsilon$ keeps more of the product structure.

KL-normalized dual potentials along the scaling iteration. The logarithmic scaling potentials stabilize as the row/column normalizations converge.

The next interactive demo keeps the iteration count high and varies the temperature. It is the quickest way to see the geometry-bias tradeoff: low temperature is geometric and sharp, high temperature is smooth and closer to independence.

Interactive panel. Use the regularization slider to compare sparse exact-looking couplings with smoother entropic plans and potentials.

Complexity bounds for Sinkhorn and comparisons with accelerated first-order methods are discussed in Altschuler et al., 2017Dvurechensky et al., 2018Knight, 2008. For a dense $n\times m$ problem, each iteration costs one multiplication by $K$ and one by $K^\top$ , so the cost scales like $Cnm$ for $C$ iterations. For fixed positive $\epsilon$ , the marginal error eventually has a linear regime, but small $\epsilon$ makes the Gibbs kernel more peaked and scaling harder.

Marginal violation along Sinkhorn half-steps for several values of $\epsilon$ . Smaller $\epsilon$ gives sharper transport geometry but slower scaling.

Remark: Separable Gaussian kernels on grids

When the samples lie on a Cartesian grid and $c(x,y)=\norm{x-y}^2$ , the Gibbs kernel is Gaussian and factorizes along coordinates. If the grid has $q$ points per axis in dimension $d$ , so that $N=q^d$ grid points are used, then

K(x,y)=\exp\!\left(-\frac{\norm{x-y}^2}{\epsilon}\right) = \prod_{\ell=1}^d \exp\!\left(-\frac{(x_\ell-y_\ell)^2}{\epsilon}\right).

(9)

Multiplication by $K$ can therefore be applied by successively multiplying along each coordinate direction, equivalently by applying one-dimensional Gaussian kernel operators along the axes. On a periodic or sufficiently padded uniform grid these are literal discrete convolutions. A direct dense one-dimensional multiplication costs $O(q^2)$ on each of the $q^{d-1}$ coordinate lines, and this is repeated for $d$ axes. Hence one Sinkhorn half-step costs

O(d\,q^{d+1})=O(d\,N^{1+1/d})

(10)

instead of $O(N^2)$ . With FFT-based or truncated Gaussian convolutions, the same separability can be pushed further, but the simple tensor-product estimate already explains why grid-based Sinkhorn can scale much better than a generic dense coupling.

Algorithm: Sinkhorn scaling

Input: Weights $\a,\b$ , cost matrix $\C$ , regularization $\epsilon>0$ , tolerance $\mathrm{tol}$ .

Output: Entropic coupling $\P$ .

Initialize: Set $\K_{ij}=e^{-\C_{ij}/\epsilon}$ , $\vD^{(0)}=\ones_m$ , $r_0=+\infty$ , and $k=0$ .

While $r_k>\mathrm{tol}$ do:

Set $k\leftarrow k+1$ .
$\uD^{(k)}=\frac{\a}{\K\vD^{(k-1)}}.$
$\vD^{(k)}=\frac{\b}{\transp{\K}\uD^{(k)}}.$
$\P^{(k)}=\diag(\uD^{(k)})\K\diag(\vD^{(k)}).$
Set $r_k=\max\{\norm{\P^{(k)}\ones_m-\a}_1,\norm{(\P^{(k)})^\top\ones_n-\b}_1\}$ .

Return $\P^{(k)}$ .

Reformulation Using Relative Entropy¶

The KL formulation identifies Sinkhorn as a projection method. It also prepares the continuous and unbalanced settings, where a reference measure is essential.

For matrices with the same total mass, the affine terms cancel and

\operatorname{KL}(P|Q) = \sum_{i,j}P_{i,j}\log\frac{P_{i,j}}{Q_{i,j}}.

(12)

On fixed-mass couplings, taking $Q=\mathbf 1_{n\times m}$ is equivalent to subtracting the Shannon--Boltzmann entropy. Taking the tensor-product reference gives the normalized formulation

\min_{P\in\mathbf U(a,b)} \langle P,C\rangle + \epsilon\operatorname{KL}(P|a\otimes b).

(13)

The tensor-product reference is nevertheless useful when supports vary. It makes explicit which entries may vanish and passes cleanly to the continuous formulation.

KL-normalized Sinkhorn dual potentials for one-dimensional Gaussian-mixture histograms. Increasing $\epsilon$ turns the hard $c$ -transform geometry into smoother log-sum-exp potentials.

Entropically regularized couplings between the red disk and blue annulus point clouds. The plans are strictly positive for every $\epsilon>0$ , but the visible mass pattern evolves from nearly radial and sparse to diffuse as $\epsilon$ increases.

General Formulation¶

The continuous formulation replaces matrices by measures and discrete KL by relative entropy. For probability measures $\alpha$ and $\beta$ , define

\mathcal{L}_{c}^{\epsilon}(\alpha,\beta) \eqdef \min_{\pi\in\Couplings(\alpha,\beta)} \int_{\X\times\Y}c(x,y)\,\d\pi(x,y) + \epsilon\operatorname{KL}(\pi|\alpha\otimes\beta).

(19)

For fixed balanced marginals, the specific product reference only matters up to additive constants, provided the reference marginals are mutually absolutely continuous with $\alpha$ and $\beta$ . Its support still matters: it determines which couplings have finite entropy.

Path-Space Schrodinger Problem¶

Schrodinger’s reciprocal problem is naturally posed on paths rather than on endpoint pairs. The Sinkhorn problem appears after the path law is reduced to its two endpoint marginals.

Unregularized Path-Space Transport¶

Let $\Omega=C([0,1];\X)$ be a path space and let $e_t(\omega)=\omega_t$ be the evaluation maps. Given a path action $\mathcal A:\Omega\to[0,+\infty]$ , the unregularized path-space problem is

\inf_{M\in\mathcal P(\Omega)} \left\{ \int_\Omega\mathcal A(\omega)\,\d M(\omega) : (e_0)_\sharp M=\alpha,\ (e_1)_\sharp M=\beta \right\}.

(21)

For quadratic Wasserstein geometry on $\RR^d$ ,

\mathcal A(\omega) = \begin{cases} \int_0^1\norm{\dot\omega_t}^2\,\d t, & \omega\text{ absolutely continuous},\\ +\infty, & \text{otherwise}. \end{cases}

(22)

The endpoint cost induced by the action is

c_{\mathcal A}(x,y) \eqdef \inf\left\{ \mathcal A(\omega): e_0(\omega)=x,\ e_1(\omega)=y \right\}.

(23)

For the quadratic action, the minimizing path is the straight segment and $c_{\mathcal A}(x,y)=\norm{x-y}^2$ .

Entropic Path-Space Problem¶

Let $R^\epsilon\in\mathcal P(\Omega)$ be a reference path law, for instance a Brownian or Langevin dynamics at noise level $\epsilon$ . The dynamic Schrodinger bridge problem is the entropy projection

\mathrm{SB}_\epsilon(\alpha,\beta) \eqdef \inf_{M\in\mathcal P(\Omega)} \left\{ \epsilon\operatorname{KL}(M|R^\epsilon): (e_0)_\sharp M=\alpha,\ (e_1)_\sharp M=\beta \right\}.

(27)

It asks for the most likely path law, relative to the prior dynamics, among all path laws matching the observed endpoints Schrödinger, 1931Léonard, 2012Léonard, 2014Chen et al., 2016.

The dynamic problem also has viscous Benamou--Brenier formulations. In one common convention,

\partial_t\rho_t+\operatorname{div}(\rho_t v_t) = \frac{\sigma}{2}\Delta\rho_t

(28)

and one minimizes a kinetic action. After absorbing the diffusion into the velocity $u_t=v_t-\frac{\sigma}{2}\nabla\log\rho_t$ , the same minimizers are obtained from

\int_0^1\!\int \left( \frac12\norm{u_t(x)}^2 + \frac{\sigma^2}{8}\norm{\nabla\log\rho_t(x)}^2 \right) \rho_t(x)\,\d x\,\d t,

(29)

up to endpoint entropy terms. The extra term is a Fisher-information penalty.

For Brownian reference dynamics on $\RR^d$ , the endpoint prior has heat-kernel density proportional to

\exp\left(-\frac{\norm{x-y}^2}{\epsilon}\right).

(33)

After rewriting this prior with respect to $\alpha\otimes\beta$ , the endpoint problem is exactly the continuous Sinkhorn problem up to an additive constant. Sinkhorn computes which endpoints should be paired; the path-space Schrodinger bridge then connects each pair by a Brownian bridge.

Endpoint couplings lifted to Brownian bridges. Increasing $\epsilon$ both softens the endpoint coupling and amplifies the Brownian fluctuations between paired endpoints.

With this terminology, the entropic problem is

\inf_{X\sim\alpha,\;Y\sim\beta} \mathbb E(c(X,Y))+\epsilon\mathcal I(X,Y).

(35)

Large $\epsilon$ favors nearly independent endpoints, while small $\epsilon$ suppresses endpoint randomness and recovers an optimal Monge--Kantorovich coupling in the limit.

Algorithm: Endpoint-to-path Schr"odinger lift

Input: Endpoint laws $\alpha,\beta$ , cost $c$ , regularization $\epsilon>0$ , reference bridges $\Rr^{\epsilon,x,y}$ .

Output: Schrodinger path law $M_\epsilon^\star$ .

Let $\pi_\epsilon^\star$ be a minimizer of the static entropic endpoint problem: $\pi_\epsilon^\star \in \argmin_{\pi\in\Couplings(\al,\be)} \int c\,\d\pi+\epsilon\KL(\pi|\al\otimes\be).$

For each endpoint pair $(x,y)$ sampled from $\pi_\epsilon^\star$ do:

Draw bridge path: $\omega\sim\Rr^{\epsilon,x,y}.$

Return $M_\epsilon^\star= \int \Rr^{\epsilon,x,y}\,\d\pi_\epsilon^\star(x,y).$

Dual of Sinkhorn¶

The dual point of view replaces couplings by potentials and soft $c$ -transforms. It is the right formulation for stabilized implementations and differentiation.

Discrete Dual¶

The KL-normalized problem has the dual

\min_{P\in\mathbf U(a,b)} \langle P,C\rangle+\epsilon\operatorname{KL}(P|a\otimes b) = \max_{f,g} \left[ \langle f,a\rangle+\langle g,b\rangle - \epsilon\sum_{i,j} \exp\left(\frac{f_i+g_j-C_{i,j}}{\epsilon}\right)a_i b_j + \epsilon \right].

(36)

The optimal potentials are linked to the scaling variables through

u_i=a_i e^{f_i/\epsilon}, \qquad v_j=b_j e^{g_j/\epsilon}.

(37)

Discrete Soft $c$ -Transforms¶

For fixed $g$ , maximizing the dual with respect to $f$ gives

f_i = -\epsilon\log \sum_j \exp\left(\frac{g_j-C_{i,j}}{\epsilon}\right)b_j.

(38)

This is a smoothed minimum.

Exponentiating the alternating soft-transform iterations recovers Sinkhorn’s algorithm. For small $\epsilon$ , one must compute the log-sum-exp terms with the usual stabilization trick: subtract the minimum before exponentiating and add it back afterward.

Soft $c$ -transforms for decreasing temperatures. A positive $\epsilon$ replaces the hard lower envelope by a log-sum-exp soft minimum.

Interactive panel. Use the epsilon and potential controls to see how the hard c-transform is softened by log-sum-exp smoothing.

Continuous Dual and Soft-Transforms¶

For compact spaces and continuous cost, the KL-regularized problem has the concave dual

\mathcal{L}_{c}^{\epsilon}(\alpha,\beta) = \sup_{f,g} \mathcal D_\epsilon(f,g),

(41)

where

\mathcal D_\epsilon(f,g) = \int f\,\d\alpha+\int g\,\d\beta - \epsilon \int \left( e^{(f(x)+g(y)-c(x,y))/\epsilon} - 1 \right) \d\alpha(x)\d\beta(y).

(42)

This is the smooth counterpart of the hard feasibility constraint $f\oplus g\le c$ from the Kantorovich dual.

Remark: Convexity properties of soft transforms

The log-sum-exp part behaves like a smoothed maximum and preserves convexity. Since the soft transform takes the negative of this quantity after inserting the cost, it preserves the usual $c$ -concavity structure. In particular, for the bilinear cost $c(x,y)=-\dotp{x}{y}$ , the transform $f^{c,\epsilon}$ is concave for any $f$ . Therefore, for the quadratic cost $c(x,y)=\norm{x-y}^2/2$ , the optimal potentials have the form $f^\star(x)=\norm{x}^2/2-\phi^\star(x)$ and $g^\star(y)=\norm{y}^2/2-\psi^\star(y)$ , where $\phi^\star$ and $\psi^\star$ are convex.

Algorithm: Log-domain Sinkhorn by soft transforms

Input: Weights $\a,\b$ , cost matrix $\C$ , regularization $\epsilon>0$ , tolerance $\mathrm{tol}$ .

Output: Entropic coupling $\P$ computed from stabilized potentials.

Initialize: Set $\gD^{(0)}=0$ , $\eta_0=+\infty$ , and $k=0$ .

While $\eta_k>\mathrm{tol}$ do:

Set $k\leftarrow k+1$ .
Compute stabilized soft transform: $\fD_i^{(k)} = -\epsilon\log\sum_j \exp\!\left(\frac{\gD_j^{(k-1)}-\C_{ij}}{\epsilon}\right)\b_j.$
Compute stabilized reverse soft transform: $\gD_j^{(k)} = -\epsilon\log\sum_i \exp\!\left(\frac{\fD_i^{(k)}-\C_{ij}}{\epsilon}\right)\a_i.$
Set $\eta_k=\max\{\norm{\fD^{(k)}-\fD^{(k-1)}}_\infty,\norm{\gD^{(k)}-\gD^{(k-1)}}_\infty\}$ , with the first term ignored for $k=1$ .

Return $\P_{ij} = \a_i\b_j \exp\!\left(\frac{\fD_i^{(k)}+\gD_j^{(k)}-\C_{ij}}{\epsilon}\right).$

Other Convex Regularizers¶

KL regularization is the case that leads to multiplicative Sinkhorn scalings. Replacing KL by another density-ratio penalty keeps the same transport constraints but changes the scalar law linking the optimal density to the dual potentials.

Let $\phi$ be an entropy function and define

\mathcal L_{c,\phi}^{\epsilon}(\alpha,\beta) \eqdef \min_{\pi\in\Couplings(\alpha,\beta)} \int c(x,y)\,\d\pi(x,y) + \epsilon D_\phi(\pi|\alpha\otimes\beta).

(46)

Proposition: Dual and Density Law for

\phi

-Regularized OT

Under standard Fenchel--Rockafellar qualification assumptions,

\mathcal L_{c,\phi}^{\epsilon}(\alpha,\beta) = \sup_{f,g} \int f\,\d\alpha+\int g\,\d\beta - \epsilon \int \phi^{*,\ge0} \left( \frac{f(x)+g(y)-c(x,y)}{\epsilon} \right) \d\alpha(x)\d\beta(y).

(47)

If the optimal plan has density $r^\star=\d\pi^\star/\d(\alpha\otimes\beta)$ and the solution is smooth and interior, then

r^\star(x,y) = (\phi')^{-1} \left( \frac{f^\star(x)+g^\star(y)-c(x,y)}{\epsilon} \right).

(48)

For KL, $\phi(r)=r\log r-r+1$ and $\phi^{*,\ge0}(s)=e^s-1$ , recovering the Sinkhorn dual. Other choices replace the exponential law by another scalar transfer function:

\begin{array}{lll} \phi(r)=r\log r-r+1 &\Rightarrow& r^\star=e^s,\\ \phi(r)=r-\log r-1 &\Rightarrow& r^\star=(1-s)^{-1}\quad(s<1),\\ \phi(r)=\frac12(r-1)^2 &\Rightarrow& r^\star=(1+s)_+, \end{array} \qquad s=\frac{f^\star\oplus g^\star-c}{\epsilon}.

(49)

Density-ratio regularizers and coupling support. KL gives the usual diffuse positive plan, the Burg barrier keeps positive but differently tailed support, and the quadratic density penalty can set entries exactly to zero through its positive-part law.

The interactive demo below separates the two effects. The left plot shows the pointwise law $r=h(s)$ , while the right plot recomputes a coupling after enforcing the marginals with that law. Changing $\epsilon$ controls how much the cost score is softened; changing the regularizer changes whether mass is spread everywhere, protected by a barrier, or clipped to a sparse support.

Interactive panel. Use the regularization-family and strength controls to compare entropic and quadratic penalties on the same transport problem.

Bregman vs. $\phi$ -Divergence Regularization¶

The previous construction regularizes OT by a density-ratio divergence. This differs from using a Bregman divergence generated by a convex functional on the space of measures.

Thus the two generalizations lead to different duals and different algorithms. Only for KL do density-ratio regularization and Bregman projection geometry coincide and reduce to multiplicative Sinkhorn scalings.

Sinkhorn Divergences¶

Sinkhorn divergences remove the entropic self-bias while retaining smoothness. They interpolate between OT-like geometry and kernel-like norms, which explains their statistical behavior.

Entropic Bias¶

The raw Sinkhorn cost is biased: for $\epsilon>0$ , minimizing $\mathcal L_c^\epsilon(\alpha,\beta)$ over $\beta$ does not generally return $\beta=\alpha$ . In the large-temperature limit, the raw value behaves like a product interaction:

For $c(x,y)=\norm{x-y}^2$ , minimizing this large-temperature limit over $\beta$ collapses toward a Dirac at the mean of $\alpha$ .

Sinkhorn Divergences¶

The standard debiasing subtracts the two self-interaction energies. This cancellation removes the large-temperature attraction toward the independent coupling; positivity is a separate property, proved below through the positive-definite kernel associated with $e^{-c/\epsilon}$ .

Debiasing by point optimization. For large $\epsilon$ , minimizing the raw entropic cost collapses atoms toward the barycenter, whereas the self-cost subtraction keeps a bimodal cloud.

The interactive demo below shows the same mechanism in a one-dimensional toy setting. Move the model cloud relative to the target and compare the raw entropic objective with its debiased version.

Interactive panel. Use the blur and separation controls to compare the raw entropic cost with the debiased Sinkhorn divergence.

Example: Large-temperature collapse for quadratic costs

The limiting functional minimized by $\al_\epsilon$ is linear in the second argument:

\be\mapsto \int V_\alpha(y)\d\beta(y), \qquad V_\alpha(y)\eqdef\int c(x,y)\d\alpha(x).

(61)

Thus any limiting minimizer is supported on $\argmin V_\alpha$ . When this minimizer is unique,

\al_\epsilon \rightharpoonup \delta_{y^\star(\alpha)}, \qquad y^\star(\alpha)=\uargmin{y} V_\alpha(y).

(62)

For the quadratic cost $c(x,y)=\norm{x-y}^2$ on $\RR^d$ , assuming $\alpha$ has finite second moment, one has $V_\alpha(y)=\norm{y-\int x\d\alpha(x)}^2+\mathrm{const}$ , so the collapse is toward the Dirac mass at the mean of $\alpha$ .

References¶

Sinkhorn, R. (1964). A relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematical Statistics, 35(2), 876–879. 10.1214/aoms/1177703591
Sinkhorn, R., & Knopp, P. (1967). Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2), 343–348. 10.2140/pjm.1967.21.343
Sinkhorn, R. (1967). Diagonal equivalence to matrices with prescribed row and column sums. American Mathematical Monthly, 74, 402–405.
Cuturi, M. (2013). Sinkhorn distances: lightspeed computation of optimal transport. Advances in Neural Information Processing Systems 26, 2292–2300.
Peyré, G., & Cuturi, M. (2019). Computational Optimal Transport with Applications to Data Sciences. Foundations and Trends in Machine Learning, 11(5–6), 355–607. 10.1561/2200000073
Altschuler, J., Weed, J., & Rigollet, P. (2017). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in Neural Information Processing Systems, 30, 1964–1974.
Dvurechensky, P., Gasnikov, A., & Kroshnin, A. (2018). Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm. In J. Dy & A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 1367–1376). PMLR.
Knight, P. A. (2008). The Sinkhorn–Knopp algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1), 261–275.
Schrödinger, E. (1931). Über die Umkehrung der Naturgesetze. Sitzungsberichte Preuss. Akad. Wiss. Berlin. Phys. Math., 144, 144–153.
Léonard, C. (2012). From the Schrödinger problem to the Monge–Kantorovich problem. Journal of Functional Analysis, 262(4), 1879–1920.
Léonard, C. (2014). A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Continuous Dynamical Systems Series A, 34(4), 1533–1574.
Chen, Y., Georgiou, T. T., & Pavon, M. (2016). On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint. Journal of Optimization Theory and Applications, 169(2), 671–691.

Entropic Regularization: Sinkhorn Algorithm

Entropic Regularization for Discrete Measures¶

Smoothing Effect¶

Entropy Barriers Versus Generic LP Barriers¶

Sinkhorn’s Algorithm¶

Reformulation Using Relative Entropy¶

General Formulation¶

Path-Space Schrodinger Problem¶

Unregularized Path-Space Transport¶

Entropic Path-Space Problem¶

Dual of Sinkhorn¶

Discrete Dual¶

Discrete Soft ccc-Transforms¶

Continuous Dual and Soft-Transforms¶

Other Convex Regularizers¶

Bregman vs. ϕ\phiϕ-Divergence Regularization¶

Sinkhorn Divergences¶

Entropic Bias¶

Sinkhorn Divergences¶

Discrete Soft $c$ -Transforms¶

Bregman vs. $\phi$ -Divergence Regularization¶