Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs

• URL: http://arxiv.org/abs/2603.26940v1
• Date: Fri, 27 Mar 2026 19:29:28 GMT
• Title: Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs
• Abstract summary: The optimal transport problem defines a geometry of probability measures which leads to a definition for weighted averages (barycenters) of measures.<n>Here, we implement a barycentric coding model for measures supported on a graph, in which the classical optimal transport geometry becomes degenerate.<n>We conclude that intrinsic gradient descent on the probability simplex provides a coherent framework for the synthesis and analysis of measures supported on graphs.
• Score: 3.702642055407484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The optimal transportation problem defines a geometry of probability measures which leads to a definition for weighted averages (barycenters) of measures, finding application in the machine learning and computer vision communities as a signal processing tool. Here, we implement a barycentric coding model for measures which are supported on a graph, a context in which the classical optimal transport geometry becomes degenerate, by leveraging a Riemannian structure on the simplex induced by a dynamic formulation of the optimal transport problem. We approximate the exponential mapping associated to the Riemannian structure, as well as its inverse, by utilizing past approaches which compute action minimizing curves in order to numerically approximate transport distances for measures supported on discrete spaces. Intrinsic gradient descent is then used to synthesize barycenters, wherein gradients of a variance functional are computed by approximating geodesic curves between the current iterate and the reference measures; iterates are then pushed forward via a discretization of the continuity equation. Analysis of measures with respect to given dictionary of references is performed by solving a quadratic program formed by computing geodesics between target and reference measures. We compare our novel approach to one based on entropic regularization of the static formulation of the optimal transport problem where the graph structure is encoded via graph distance functions, we present numerical experiments validating our approach, and we conclude that intrinsic gradient descent on the probability simplex provides a coherent framework for the synthesis and analysis of measures supported on graphs.

Related papers

• Wasserstein Formulation of Reinforcement Learning. An Optimal Transport Perspective on Policy Optimization [0.0]
  We present a framework for Reinforcement Learning that views policies as maps into the Wasserstein space of action probabilities.<n>For high-dimensional problems, we parameterize the policy using a neural network and optimize it based on an ergodic approximation of the cost.
  arXiv  Detail & Related papers  (2026-04-16T08:24:23Z)
• Wasserstein Regression as a Variational Approximation of Probabilistic Trajectories through the Bernstein Basis [41.99844472131922]
  Existing approaches often ignore the geometry of the probability space or are computationally expensive.<n>A new method is proposed that combines the parameterization of probability trajectories using a Bernstein basis and the minimization of the Wasserstein distance between distributions.<n>The developed approach combines geometric accuracy, computational practicality, and interpretability.
  arXiv  Detail & Related papers  (2025-10-30T15:36:39Z)
• Fast data inversion for high-dimensional dynamical systems from noisy measurements [10.060455365145106]
  We develop a scalable approach for a flexible latent factor model for high-dimensional dynamical systems.<n>By applying our method to geodetic measurements in the Cascadia region, our estimated slip better agrees with independently measured seismic data of tremor events.
  arXiv  Detail & Related papers  (2025-01-02T16:25:57Z)
• Quantum State Assignment Flows [3.7886425043810905]
  This paper flows for assignment as state spaces representing data associated with layers of an underlying weighted graph. The novel approach for data representation and analysis, including the representation of data across the graph by and entanglementization, is presented.
  arXiv  Detail & Related papers  (2023-06-30T18:29:14Z)
• Counting Phases and Faces Using Bayesian Thermodynamic Integration [77.34726150561087]
  We introduce a new approach to reconstruction of the thermodynamic functions and phase boundaries in two-parametric statistical mechanics systems. We use the proposed approach to accurately reconstruct the partition functions and phase diagrams of the Ising model and the exactly solvable non-equilibrium TASEP.
  arXiv  Detail & Related papers  (2022-05-18T17:11:23Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Alternating minimization algorithms for graph regularized tensor completion [8.26185178671935]
  We consider a Canonical Polyadic (CP) decomposition approach to low-rank tensor completion (LRTC) The usage of graph regularization entails benefits in the learning accuracy of LRTC, but at the same time, induces coupling graph Laplacian terms. We propose efficient alternating minimization algorithms by leveraging the block structure of the underlying CP decomposition-based model.
  arXiv  Detail & Related papers  (2020-08-28T23:20:49Z)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  We introduce a new dual formulation for the regularized Wasserstein barycenter problem. We establish strong duality and use the corresponding primal-dual relationship to parametrize the barycenter implicitly using the dual potentials of regularized transport problems.
  arXiv  Detail & Related papers  (2020-08-28T08:28:06Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
  We propose a novel numerical scheme to optimize the gradient flows for learning energy-based models (EBMs) We derive a second-order Wasserstein gradient flow of the global relative entropy from Fokker-Planck equation. Compared with existing schemes, Wasserstein gradient flow is a smoother and near-optimal numerical scheme to approximate real data densities.
  arXiv  Detail & Related papers  (2019-10-31T02:26:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.