More Like this

1. Nonlocal-Interaction Equation on Graphs: Gradient Flow Structure and Continuum Limit

   https://doi.org/10.1007/s00205-021-01631-w  

   Esposito, Antonio; Patacchini, Francesco S.; Schlichting, André; Slepčev, Dejan (May 2021, Archive for Rational Mechanics and Analysis)

   null (Ed.)

   Abstract We consider dynamics driven by interaction energies on graphs. We introduce graph analogues of the continuum nonlocal-interaction equation and interpret them as gradient flows with respect to a graph Wasserstein distance. The particular Wasserstein distance we consider arises from the graph analogue of the Benamou–Brenier formulation where the graph continuity equation uses an upwind interpolation to define the density along the edges. While this approach has both theoretical and computational advantages, the resulting distance is only a quasi-metric. We investigate this quasi-metric both on graphs and on more general structures where the set of “vertices” is an arbitrary positive measure. We call the resulting gradient flow of the nonlocal-interaction energy the nonlocal nonlocal-interaction equation (NL $$^2$$ 2 IE). We develop the existence theory for the solutions of the NL $$^2$$ 2 IE as curves of maximal slope with respect to the upwind Wasserstein quasi-metric. Furthermore, we show that the solutions of the NL $$^2$$ 2 IE on graphs converge as the empirical measures of the set of vertices converge weakly, which establishes a valuable discrete-to-continuum convergence result. 

   more » « less
2. Map-matching using shortest paths

   https://doi.org/10.1145/3191801.3191812  

   Chambers, Erin; Fasy, Brittany Terese; Wang, Yusu; Wenk, Carola (January 2018, IWISC)

   We consider several variants of the map-matching problem, which seeks to find a path Q in graph G that has the smallest distance to a given trajectory P (which is likely not to be exactly on the graph). In a typical application setting, P models a noisy GPS trajectory from a person traveling on a road network, and the desired path Q should ideally correspond to the actual path in G that the person has traveled. Existing map-matching algorithms in the literature consider all possible paths in G as potential candidates for Q. We find solutions to the map-matching problem under different settings. In particular, we restrict the set of paths to shortest paths, or concatenations of shortest paths, in G. As a distance measure, we use the Fréchet distance, which is a suitable distance measure for curves since it takes the continuity of the curves into account. 

   more » « less
3. Path constrained unbalanced optimal transport

   https://doi.org/10.1088/1361-6544/ade21d  

   Bauer, Martin; Charon, Nicolas; Needham, Tom; Nishino, Mao (June 2025, Nonlinearity)

   Abstract Dynamical formulations of optimal transport (OT) frame the task of comparing distributions as a variational problem which searches for a path between distributions minimizing a kinetic energy functional. In applications, it is frequently natural to require paths of distributions to satisfy additional conditions. Inspired by this, we introduce a model for dynamical OT which incorporates constraints on the space of admissible paths into the framework of unbalanced OT, where the source and target measures are allowed to have a different total mass. Our main results establish, for several general families of constraints, the existence of solutions to the variational problem which defines this path constrained unbalanced OT framework. These results are primarily concerned with distributions defined on an Euclidean space, but we extend them to distributions defined over parallelizable Riemannian manifolds as well. We also consider metric properties of our framework, showing that, for certain types of constraints, our model defines a metric on the relevant space of distributions. This metric is shown to arise as a geodesic distance of a Riemannian metric, obtained through an analogue of Otto’s submersion in the classical OT setting. 

   more » « less
4. A comparison principle for semilinear Hamilton–Jacobi–Bellman equations in the Wasserstein space

   https://doi.org/10.1007/s00526-024-02718-4  

   Daudin, Samuel; Seeger, Benjamin (April 2024, Calculus of Variations and Partial Differential Equations)

   Abstract The goal of this paper is to prove a comparison principle for viscosity solutions of semilinear Hamilton–Jacobi equations in the space of probability measures. The method involves leveraging differentiability properties of the 2-Wasserstein distance in the doubling of variables argument, which is done by introducing a further entropy penalization that ensures that the relevant optima are achieved at positive, Lipschitz continuous densities with finite Fischer information. This allows to prove uniqueness and stability of viscosity solutions in the class of bounded Lipschitz continuous (with respect to the 1-Wasserstein distance) functions. The result does not appeal to a mean field control formulation of the equation, and, as such, applies to equations with nonconvex Hamiltonians and measure-dependent volatility. For convex Hamiltonians that derive from a potential, we prove that the value function associated with a suitable mean-field optimal control problem with nondegenerate idiosyncratic noise is indeed the unique viscosity solution. 

   more » « less
5. The Gromov–Wasserstein Distance Between Spheres

   https://doi.org/10.1007/s10208-024-09678-3  

   Arya, Shreya; Auddy, Arnab; Clark, Ranthony A; Lim, Sunhyuk; Mémoli, Facundo; Packer, Daniel (September 2024, Foundations of Computational Mathematics)

   Abstract The Gromov–Wasserstein distance—a generalization of the usual Wasserstein distance—permits comparing probability measures defined on possibly different metric spaces. Recently, this notion of distance has found several applications in Data Science and in Machine Learning. With the goal of aiding both the interpretability of dissimilarity measures computed through the Gromov–Wasserstein distance and the assessment of the approximation quality of computational techniques designed to estimate the Gromov–Wasserstein distance, we determine the precise value of a certain variant of the Gromov–Wasserstein distance between unit spheres of different dimensions. Indeed, we consider a two-parameter family$$\{d_{{{\text {GW}}}p,q}\}_{p,q=1}^{\infty }$$ ${\left\{d_{\text{GW}p,q}\right\}}_{p,q=1}^{\infty }$of Gromov–Wasserstein distances between metric measure spaces. By exploiting a suitable interaction between specific values of the parameterspandqand the metric of the underlying spaces, we are able to determine the exact value of the distance$$d_{{{\text {GW}}}4,2}$$ $d_{\text{GW}4,2}$between all pairs of unit spheres of different dimensions endowed with their Euclidean distance and their uniform measure. 

   more » « less