Unifying Discrete and Semi-Discrete Optimal Transport via Dual Potentials — E8 Intelligence Research

Abstract

FINDING: Discrete optimal transport (OT) on grids reduces to solving dual potentials via discrete harmonic equations, with network simplex providing exact solutions; semi-discrete OT bridges discrete measures to continuous ones via Laguerre tessellations, whose cell volumes encode dual potentials. | MATH: Kantorovich dual: \(\max_{\phi,\psi} \sum_i a_i \phi_i + \sum_j b_j \psi_j\) s.t. \(\phi_i + \psi_j \le c_{ij}\). Discrete dual potentials satisfy \(\Delta \phi = \rho - \sigma\) (discrete Poisson equation) on the grid, where \(\Delta\) is the graph Laplacian. Network simplex pivots on spanning trees; complexity \(O(n^3 \log n)\) worst-case, but parallel implementations exploit grid structure. Semi-discrete: \(\psi_j = \min_i (|x - x_i|^2/2 - \phi_i)\); cell volumes \(V_i(\phi) = \int_{L_i(\phi)} dx\) must match \(a_i\), solved by Newton iterations on \(\phi\). | CONNECTION: The dual potentials on a regular grid are discrete harmonic functions — their discrete Laplacian zero modes cor Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com