Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data

1 Introduction

• Prior barycenter theory established existence, uniqueness, and transport characterization for sufficiently regular marginals, while practical data often consists of discrete probability measures.The cited regularity conditions are that marginals vanish on small sets or have densities with respect to Lebesgue measure.Source: §1 · p. 2
• Discrete marginals guarantee that barycenters are discrete, so finite-dimensional linear programming can characterize all possible optimal barycenters.The paper studies their properties using polyhedral theory.Source: §1 · p. 2
• For eight monthly-demand distributions, the computed barycenter has 63 support locations, against a theoretical upper bound of 65.The figure contrasts this computed support with 12,870 possible support points.Source: Figure 2 · p. 3
• Discrete barycenters always include a solution with provably sparse finite support and admit non-mass-splitting optimal transports to each marginal.Such transports generally do not exist between two discrete measures absent special mass-balance conditions.Source: §1 · p. 3
• The inventory example treats monthly demand distributions as marginals and interprets their barycenter as facility locations minimizing total squared transportation cost.The example illustrates the theory for hypothetical demand shapes over a fixed set of goods.Source: Figure 1 · p. 2, §1 · p. 3

• Every discrete barycenter is supported on the finite set of possible centroids formed from one support point per marginal, enabling finite-dimensional optimization.The paper uses a finite-dimensional linear program and polyhedral theory to analyze the discrete barycenters themselves.Source: §2 · pp. 3–5
• Optimal transports from a discrete barycenter to each marginal do not split mass, and their displacements balance at each barycenter support point.Theorem 1 also gives convex-function gradients that realize Wasserstein-optimal transport to each marginal.Source: Figure 3 · p. 4, §2 · p. 5
• A barycenter exists with support size at most the sum of marginal support sizes minus N plus 1, and this bound is best possible.The paper demonstrates tightness using one marginal with W uniformly weighted support points and all other marginals concentrated at single points.Source: §2 · p. 5
• When all marginals lie on a uniform grid, a barycenter exists on a refined grid whose dimensions depend on N and the original grid dimensions.The corollary specifies refined dimensions beginning with N(L1 − 1) + 1.Source: §2 · p. 5

3.1 Existence of Discrete Barycenters

• A discrete barycenter is the law of the coordinatewise average of an optimally coupled tuple, and every barycenter is supported on S.The constructed average law is a minimizer; the proof also shows that barycenters cannot have support outside S.Source: §3.1 · pp. 6–7

3.2 Linear Programming and Optimal Transport

• The exact barycenter LP links N transportation problems through common mass variables, and any optimizer represents a barycenter.The LP is bounded and feasible; for N = 2, it can be replaced by a network flow LP.Source: §3.2 · p. 8

3.3 Sparsity and Transportation Schemes

• Location-fixed transportation schemes correspond to N-star transports and yield discrete measures whose support is no larger than the number of positive scheme entries.The lemma also establishes that these schemes can represent a discrete measure and transport at the same cost as its N-star transport.Source: §3.3 · p. 10
• A minimum-cost location-fixed transportation scheme has an optimal basic solution whose positive-entry count is bounded by the rank of the equality-constraint matrix.This gives a provably small-support optimal scheme.Source: §3.3 · pp. 11–12
• For each i = 2, . . . , N, one equality-constraint row is redundant, giving N − 1 redundant rows.For fixed i, summing the constraint rows gives the all-ones vector.Source: §3.3 · p. 12
• A minimum location-fixed transportation scheme yields a barycenter with support bounded by Σ_i S_i − N + 1.The proof starts from an optimal transport for a barycenter and uses the minimum-cost scheme to construct another barycenter.Source: §3.3 · p. 12

Proof (of Corollary 1)

• For marginals on an L1 × . . . × Ld grid, the barycenter support lies on an (N(L1 − 1) + 1) × . . . × (N(Ld − 1) + 1) grid.The proof also notes that the absolute support bound follows from Theorem 2; the supplied passage does not include the relative-density bound.Source: Proof (of Corollary 1) · p. 12

4 Computations

• The eight monthly demand distributions over nine California cities are based on population and average high temperatures, with temperatures drawn from observed monthly averages.The data is artificially generated for exposition; scaling from eight to twelve months was avoided to reduce computational burdens.Source: §4 · p. 13
• Proposition 1 bounds the barycenter’s finite covering set, while Theorem 2 bounds its support size uniformly over rearrangements of marginal masses and locations.The covering set supports finite-dimensional linear programming to obtain all possible optimal barycenters.Source: §4 · p. 13
• 63 support points receive mass, versus the Theorem 2 upper bound of 65 and 12,870 possible points; this is 0.5% of the possible support.The linear program had 939,510 variables and 103,032 constraints, and solved in 505 seconds on a 2.3 GHz Intel Core i7 MacBook Pro.Source: §4 · p. 13
• The barycenter admits optimal maps to each monthly marginal that do not split mass, so inventory at each barycenter support point ships to exactly one city each month.The example also states that each city is at the exact center of its eight monthly transportation plans.Source: §4 · p. 13