Barycentric coding on a graph
The purpose of this page is to give you a sense of what is happening geometrically when we talk about "barycentric coding of measures on graphs".
Barycenters
The word "barycenter" is typically associated with a physics problem about finding the center of mass. Here, we're using it in a slightly more general way — we've got a collection of points (measures) in a metric space, and we want to find their weighted center of mass. For the sake of visualization, we've just got three points here, so the possible weights that we can assign to the points are \[\lambda = (\lambda_{1}, \lambda_{2}, \lambda_{3}) : \sum \lambda_{i} = 1,\ \lambda_{i} > 0.\] The set of all such \(\lambda\) is represented by the panel on the left — you can click inside the triangle to choose a particular collection of weights, and the weighted center of mass is computed in two different geometries in the other panels.
The central panel is the trivial thing to do. Given a collection of probability measures on a graph, you could combine them directly by linearly interpolating their probability mass functions — but this isn't really transport, since the mass just teleports from one place to another. What's more interesting to do is to solve a certain optimal transport problem, to obtain the figure on the right, where mass moves continuously between configurations. For details about this demo, you can see my code on GitHub, or you can read "Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs" on the Papers page.
λ = (, , )
Linear mixture Σ λiνi
spread
Transport barycenter νλ
spread
Circle area is proportional to mass, on the same scale in both graphs. Spread is the root-mean-square distance of the mass from its own center, measured in grid steps.
An interactive demo highlighting the geometry of barycentric coding of measures on graphs.
Real Wasserstein barycenters, computed by graphtransport-py's shooting solver on a 7×7 grid (precomputed).
Color palettes
UNDER CONSTRUCTION: This demo recreates an experiment which originally appeared in Bonneel, Peyré & Cuturi's 2016 paper "Wasserstein barycentric coordinates: histogram regression using optimal transport", where the authors used regularized transport via the Sinkhorn algorithm to perform color palette transfers. This page features a recreation of their experiment, and an adaptation of it via graph transportation. Further details and explanation TK
λ = (, , )
- as painted
Σ λiνi
RMS color shift ΔE
Painting 4, recolored toward νλ
RMS color shift ΔE
Running it backwards
As painted, \(\mu\)
Recolored toward \(\nu_{\hat\lambda}\)
\(\hat\lambda\) = (, , )
RMS color shift ΔE
Two geometries
λ = (, , )
- Sinkhorn \(\hat\lambda\)
- Graph \(\hat\lambda\)
Sinkhorn W₂ in color space
RMS color shift ΔE
Graph transport on the color grid
RMS color shift ΔE
Both paintings are recolored the same way; only the barycenter they are recolored toward differs. The strips show each barycenter's palette.
Entropic barycenters computed by graphtransport-py's Sinkhorn solver on about 2,300 CIELAB colors, with squared Lab distance as the ground cost. They are precomputed on a lattice of 66 weights and blended in between. λ̂ is found by differentiating through the Sinkhorn iterations (Bonneel, Peyré & Cuturi 2016). In the comparison, the graph barycenters are solved as second-order cone programs by graphtransport-py at 28 weights. The graph's λ̂ comes from the Gram matrix of geodesic potentials at the painting's own palette, so each method recovers its weights in its own way. Paintings are public domain, via Wikimedia Commons: .