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 …

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β^ …

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 …

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 propose a fast and scalable algorithm to project a given density on a set of structured measures defined over a compact 2D domain. The measures can be discrete or supported on curves for instance. The proposed principle and algorithm are a natural generalization of previous results revolving around the generation of blue-noise point distributions, such as Lloyd's algorithm or more advanced techniques based on power diagrams. We analyze the convergence properties and propose new approaches to accelerate the generation of point distributions. We also design new algorithms to project curves onto spaces of curves with bounded length and curvature or speed and acceleration. We illustrate the algorithm's interest through applications in advanced sampling theory, non-photorealistic rendering and path planning.