Two complementary constructions improve the usability of transport without abandoning its geometry. Sinkhorn divergences remove the self-interaction bias of entropy. Semi-discrete transport keeps the source continuous and the target finite, converting the dual problem into a smooth concave optimization over weighted geometric cells.
Debiasing entropic transport
Definition. The Sinkhorn divergence is \[ S_\varepsilon(\mu,\nu) = \operatorname{OT}_\varepsilon(\mu,\nu) -\frac12\operatorname{OT}_\varepsilon(\mu,\mu) -\frac12\operatorname{OT}_\varepsilon(\nu,\nu). \] The two self-costs remove the entropic preference for diffuse couplings.
Definiteness. For the usual negative-type ground costs, including standard powers of Euclidean distance in their admissible range, \(S_\varepsilon(\mu,\nu)\ge0\) and \[ S_\varepsilon(\mu,\nu)=0\quad\Longleftrightarrow\quad\mu=\nu. \] Symmetry follows when the cost is symmetric.
The statement is cost dependent: debiasing an arbitrary asymmetric or non-negative-type cost need not produce a metric-like divergence. Even in the favorable case, the triangle inequality is not generally asserted.
Interpolation between transport and kernel discrepancies
Two limiting regimes. Under suitable integrability, \[ \lim_{\varepsilon\downarrow0}S_\varepsilon(\mu,\nu) =\operatorname{OT}_0(\mu,\nu), \] while \[ \lim_{\varepsilon\to\infty}S_\varepsilon(\mu,\nu) = \int c\,\mathrm{d}\mu\,\mathrm{d}\nu -\frac12\int c\,\mathrm{d}\mu\,\mathrm{d}\mu -\frac12\int c\,\mathrm{d}\nu\,\mathrm{d}\nu. \] The latter is an energy-distance or maximum-mean-discrepancy form when \(-c\) induces a positive kernel modulo constants.
Proof idea. The small-\(\varepsilon\) statement follows from the zero-temperature convergence of each term, noting that the unregularized self-costs vanish. For large \(\varepsilon\), each entropic optimizer approaches the product coupling. Substitute the three product couplings into the debiased combination; the leading entropic constants cancel.
Statistical smoothing and bias
For fixed \(\varepsilon>0\), positive kernels make dual potentials smooth functions of the marginals, so \(S_\varepsilon(\widehat\mu_n,\widehat\nu_m)\) often has root-sample Gaussian limits under substantially weaker dimensional conditions than unregularized transport. If \(\varepsilon=\varepsilon_n\downarrow0\), inference must balance three terms: \[ \text{total error} = \text{sampling error} +\text{entropic bias} +\text{numerical error}. \] Sending \(\varepsilon_n\) to zero too quickly restores the nonsmooth and dimension-sensitive behavior of ordinary transport.
The semi-discrete setting
Definition. Let the source be \(\mu=\rho(x)\,\mathrm{d}x\) on \(\Omega\subset\mathbb R^d\), and let \[ \nu=\sum_{j=1}^Nb_j\delta_{y_j},\qquad b_j>0. \] Semi-discrete transport seeks a measurable partition of \(\Omega\) into cells of masses \(b_j\), sending each cell to \(y_j\).
Laguerre cells and the dual objective
Definition. For weights \(\psi\in\mathbb R^N\), define \[ L_j(\psi) = \{x:c(x,y_j)-\psi_j \le c(x,y_k)-\psi_k\ \text{for every }k\}. \] These are Laguerre cells. For quadratic cost they are power cells, bounded by affine hyperplanes.
Semi-discrete dual. The dual problem is the unconstrained concave maximization \[ \max_{\psi\in\mathbb R^N} \Phi(\psi), \qquad \Phi(\psi) = \sum_{j=1}^Nb_j\psi_j +\int_\Omega\min_j\{c(x,y_j)-\psi_j\}\,\mathrm{d}\mu(x). \] At a maximizer, \(\mu(L_j(\psi))=b_j\) for every \(j\), and the optimal map is \[ T(x)=y_j\quad\text{for }x\in L_j(\psi). \]
Proof. In the Kantorovich dual, optimize the source potential pointwise: \[ \varphi(x)=\min_j\{c(x,y_j)-\psi_j\}. \] Substitution gives \(\Phi\). If cell boundaries have zero \(\mu\)-mass, differentiation under the integral yields \[ \frac{\partial\Phi}{\partial\psi_j} =b_j-\mu(L_j(\psi)). \] Thus stationarity is exactly the cell-mass condition. Complementary slackness then sends each cell to its defining target point.
Power diagrams for quadratic cost
For \(c(x,y)=\tfrac12|x-y|^2\), \[ L_j(\psi) = \left\{ x:x\cdot(y_k-y_j) \le\frac{|y_k|^2-|y_j|^2}{2}+\psi_j-\psi_k \ \forall k \right\}. \] Hence each cell is a convex polyhedron. Changing \(\psi_j\) moves its facets without moving the sites \(y_j\); the weights are exactly the variables required to match prescribed cell masses.
Hessian and Newton geometry
Hessian structure. Assume \(\rho\) is continuous and positive and cells meet regularly. For \(i\ne j\), \[ \frac{\partial^2\Phi}{\partial\psi_i\partial\psi_j} = \int_{F_{ij}} \frac{\rho(x)} {|\nabla_xc(x,y_i)-\nabla_xc(x,y_j)|} \,\mathrm{d}\mathcal H^{d-1}(x), \] where \(F_{ij}=L_i\cap L_j\) is the common facet, and \[ \frac{\partial^2\Phi}{\partial\psi_i^2} =-\sum_{j\ne i}\frac{\partial^2\Phi}{\partial\psi_i\partial\psi_j}. \] Thus the Hessian is a negative weighted graph Laplacian.
Proof idea. Perturbing \(\psi_j\) moves only facets adjacent to \(L_j\). The coarea formula converts normal facet speed into first-order cell-mass change, producing the boundary integral. Total mass is invariant under adding a common constant to all weights, so row sums vanish. Positivity of facet weights makes the Hessian negative semidefinite, with constants as its gauge nullspace when the adjacency graph is connected.
After fixing a gauge such as \(\sum_j\psi_j=0\), Newton's method solves \[ D^2\Phi(\psi)\,\Delta\psi=-\nabla\Phi(\psi). \] Damping keeps all cells nonempty and ensures ascent. The Laplacian structure explains both fast local convergence and ill-conditioning when cells nearly disappear.
A one-dimensional cell calculation
Example. Let \(y_1<y_2\) and \(c(x,y)=\tfrac12|x-y|^2\). The boundary \(r\) between the two cells satisfies \[ \frac12|r-y_1|^2-\psi_1 = \frac12|r-y_2|^2-\psi_2, \] hence \[ r=\frac{y_1+y_2}{2}+\frac{\psi_1-\psi_2}{y_2-y_1}. \] The mass condition \(F_\mu(r)=b_1\) determines the weight difference. Thus the semi-discrete dual recovers the quantile boundary exactly.
Consistency under discretization
If discrete targets \(\nu_N\to\nu\) in \(W_2\), stability gives convergence of semi-discrete optimal values. Under uniqueness and regularity, the cell maps converge in measure to the Brenier map. This makes semi-discrete transport both a geometric solver and a principled map estimator, provided the discretization and density estimation errors are controlled.