Research map / Learning theory and algorithms / Optimal transport
A Unified Approach for Computing Wasserstein Barycenters of Discrete and Continuous Measures
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FRBary, a primal mirror descent (KL/Fisher-Rao) method that computes exact unregularized Wasserstein barycenters for discrete, continuous, and mixed inputs, with O(log T/sqrt T) convergence.
Problem
Computing the exact (unregularized) Wasserstein barycenter of measure-valued inputs, which existing methods handle only for discrete point clouds or for continuous densities on regular grids, not both.
Approach
Mirror descent on absolutely continuous measures with negative-entropy mirror map: each step multiplies the density by exp(-eta times the weighted sum of Kantorovich potentials to the inputs); discrete inputs are handled via semi-discrete OT, so iterates stay absolutely continuous while converging to the exact discrete barycenter.</academic_definition>
Key results
- On MNIST digit-3 barycenter (n=10), FRBary achieves W2 error 1.360e-4 and L2 error 1.573e-4, lower than EWB (1.904e-4, 2.875e-4) and DSB (3.237e-4, 5.582e-4).
- On heterogeneous inputs, FRBary takes 275-357 s versus 609-802 s for the exact free-support POT method.
- Theory: min objective gap decays at O(log T/sqrt T) under convexity and compactness of the domain, with a KL-based bound for absolutely continuous inputs.
Surprising findings
- The Sinkhorn free-support method tends to push support points toward the boundary of the output shape, giving unsatisfactory barycenters despite lower runtime in one case.
Limitations
- Current implementation focuses on 2D and 3D measures.
- Convergence rate for discrete inputs has an extra log T factor and requires inputs to lie strictly inside the domain.
- Discretization-based methods scale poorly beyond moderate dimensions; neural variant is less accurate.
Experimental setup
Datasets: MNIST Swiss roll point cloud (10^4 samples) synthetic 2D/3D Gaussian point clouds color palette samples from two images
Benchmarks: MNIST digit-3 barycenter vs LP ground truth 2D/3D Gaussian barycenters vs closed form heterogeneous input barycenters vs POT free-support methods
Metrics: W2 distance L2 distance computation time (seconds) mean and covariance distance to ground truth
Baselines: exact free-support barycenter (POT) Sinkhorn free-support barycenter (POT) entropic Wasserstein barycenter (EWB) debiased Sinkhorn barycenter (DSB) Bures-Wasserstein gradient descent LP ground truth
Builds on: Sobolev gradient barycenter (Yang et al.) entropic Wasserstein barycenter (Cuturi & Doucet) debiased Sinkhorn barycenter Bures-Wasserstein gradient descent
Closest papers by meaning
- Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization (ICLR 2021 · similarity 0.92)
- Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization (ICML 2025 · similarity 0.90)
- Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.87)
- Finding Wasserstein Ball Center: Efficient Algorithm and The Applications in Fairness (ICML 2025 · similarity 0.87)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.87)
- Mirror and Preconditioned Gradient Descent in Wasserstein Space (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.