A Grid Efficient Transport Optimization Model for the Wasserstein Barycenter Problem

We propose the Grid Efficient Transport Optimization Linear Programming (GETO-LP) model, a novel formulation of the Fixed-Support Wasserstein barycenter problem for $M$ probability distributions supported on $d$-dimensional grids. While standard LP models require $O(M{N}^2)$ variables, the GETO-LP model requires only $O(dM{N}^{1+\frac{1}{d}})$, with $N$ being the total number of points in the grid support. Despite the reduced number of variables, our formulation is exact, meaning that its solution fully characterizes both the barycenter $\nu$ and the optimal transport plans between $\nu$ and each of the $M$ input distributions without additional optimization steps. We validate the GETO-LP model via extensive comparisons with classical and entropic regularization solvers, demonstrating its effectiveness on both synthetic data and real-world applications such as color palette manipulation and medical data averaging. Overall, our approach provides an effective formulation for the Wasserstein barycenter problem, offering a memory-efficient alternative that naturally integrates with other existing computational frameworks.