Semi-discrete quadratic Wasserstein energy and state-dependent Langevin exploration

In this paper we develop a numerical method for solving a class of optimization problems known as optimal location or quantization problems. The target energy can be written either in terms of atomic measures and the Wasserstein distance or in terms of weighted points and power diagrams (generalized Voronoi diagrams). The latter formulation is more suitable for computation. We show that critical points of the energy are centroidal power diagrams, which are generalizations of centroidal Voronoi tessellations, and that they can be approximated by a generalization of Lloyd's algorithm (Lloyd's algorithm is a common method for finding centroidal Voronoi tessellations). We prove that the algorithm is energy decreasing and prove a convergence theorem. Numerical experiments suggest that the algorithm converges linearly. We illustrate the algorithm in two and three dimensions using simple models of optimal location and crystallization. In particular, we test a conjecture about the optimality o …

Numerical simulations of the air in the atmosphere and water in the oceans are essential for numerical weather prediction. The state-of-the-art for performing these fluid simulations relies on an Eulerian viewpoint, in which the fluid domain is discretized into a mesh, and the governing equations describe the fluid motion as it passes through each cell of the mesh. However, it is unclear whether a Lagrangian viewpoint, in which the fluid is discretized by a collection of particles, can outperform Eulerian simulations in global atmospheric simulations. To date, Lagrangian approaches have shown promise, but tend to produce smoother solutions. In this work, a new Lagrangian method is developed to simulate the atmosphere in which particles are represented with spherical power cells. We introduce an efficient algorithm for computing these cells which are then used to discretize the spherical shallow water equations. Mass conservation is enforced by solving a semi-discrete optimal transport …

We develop a discrete optimal transport framework for analyzing simulated annealing algorithms on finite state spaces. Building on the discrete Wasserstein metric introduced by Maas (J. Funct. Anal., 2011), we define a generalized discrete Wasserstein-2 distance and the associated notion of \emph{discrete action} for paths of probability measures on graphs. Using these tools, we establish non-asymptotic convergence guarantees for simulated annealing: the KL divergence between the algorithm's output and the target distribution is controlled by the discrete action of the annealing path. This can be viewed as the discrete counterpart of the action-based analysis of annealed Langevin dynamics in continuous spaces by Guo, Tao, and Chen (ICLR 2025). As applications, we analyze simulated annealing for two fundamental models in statistical physics. For the \emph{mean-field Ising model}, we show that annealed single-site Glauber dynamics achieves $\varepsilon$ error in KL divergence in $O(n^5β^ …

Efficient algorithms for solving optimal transport problems are important for measuring and optimizing distances between functions. In the $L^2$ semi-discrete context, this problem consists of finding a map from a continuous density function to a discrete set of points so as to minimize the transport cost, using the squared Euclidean distance as the cost function. This has important applications in image stippling, clustering, resource allocation and in generating blue noise point distributions for rendering. Recent algorithms have been developed for solving the semi-discrete problem in $2d$ and $3d$, however, algorithms in higher dimensions have yet to be demonstrated, which rely on the efficient calculation of the power diagram (Laguerre diagram) in higher dimensions. Here, we introduce an algorithm for computing power diagrams, which extends to any topological dimension. We first evaluate the performance of the algorithm in $2d-6d$. We then restrict our attention to four-dimensional …

We develop a semi-discrete optimal transport scheme for the compressible semi-geostrophic equations, a system that plays an important role in modelling large-scale atmospheric dynamics and frontogenesis. Unlike the incompressible case, the compressible equations involve variable density and internal energy, but can be recast into a variational framework that naturally couples the dynamics with an optimal transport formulation. This is done by a change to the so-called geostrophic coordinates, via a transformation inspired by the incompressible case. The discrete version of this variational formulation provides the basis for a numerical particle scheme. The implementation of this scheme presents considerable challenges, due to a non-quadratic cost function and parabolic $c$-Laguerre cells. To address these challenges, we use $c$-exponential charts to construct $c$-Laguerre tessellations efficiently, ensuring conservation of mass and energy while preserving key geometric structures. We a …