Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms

DOI10.1007/S00245-022-09911-XzbMATH Open1502.90023arXiv2112.03581OpenAlexW4309332481MaRDI QIDQ2096952FDOQ2096952

Authors: Florian Heinemann, Marcel Klatt, Axel Munk 

Publication date: 11 November 2022

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: The purpose of this paper is to provide a systematic discussion of a generalized barycenter based on a variant of unbalanced optimal transport (UOT) that defines a distance between general non-negative, finitely supported measures by allowing for mass creation and destruction modeled by some cost parameter. They are denoted as Kantorovich-Rubinstein (KR) barycenter and distance. In particular, we detail the influence of the cost parameter to structural properties of the KR barycenter and the KR distance. For the latter we highlight a closed form solution on ultra-metric trees. The support of such KR barycenters of finitely supported measures turns out to be finite in general and its structure to be explicitly specified by the support of the input measures. Additionally, we prove the existence of sparse KR barycenters and discuss potential computational approaches. The performance of the KR barycenter is compared to the OT barycenter on a multitude of synthetic datasets. We also consider barycenters based on the recently introduced Gaussian Hellinger-Kantorovich and Wasserstein-Fisher-Rao distances.

Full work available at URL: https://arxiv.org/abs/2112.03581

Recommendations

• Unbalanced optimal transport: dynamic and Kantorovich formulations
• Unbalanced optimal total variation transport problems and generalized Wasserstein barycenters
• Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)
• Hellinger–Kantorovich barycenter between Dirac measures
• Barycenters in the Hellinger-Kantorovich space

zbMATH Keywords

barycenterunbalanced optimal transportultrametric treesmulti-marginal transportWassersteinKantorovich-Rubinstein

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Trees (05C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Transportation, logistics and supply chain management (90B06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Discrete location and assignment (90B80)

Cites Work

• Measure theory. Vol. I and II
• Computational optimal transport. With applications to data sciences
• Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• The space of ultrametric phylogenetic trees
• Barycenters in the Wasserstein space
• Scaling algorithms for unbalanced optimal transport problems
• Discrete Wasserstein barycenters: optimal transport for discrete data
• Wasserstein dictionary learning: optimal transport-based unsupervised nonlinear dictionary learning
• An invitation to statistics in Wasserstein space
• Title not available (Why is that?)
• Optimal Transport
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• Linear and nonlinear programming
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization.
• Title not available (Why is that?)
• Existence and consistency of Wasserstein barycenters
• A fixed-point approach to barycenters in Wasserstein space
• Numerical methods for matching for teams and Wasserstein barycenters
• Iterative Bregman projections for regularized transportation problems
• Sliced and Radon Wasserstein barycenters of measures
• An interpolating distance between optimal transport and Fisher-Rao metrics
• Shape recognition via Wasserstein distance
• Title not available (Why is that?)
• Free boundaries in optimal transport and Monge-Ampère obstacle problems
• Generalized Wasserstein distance and its application to transport equations with source
• THE MULTI-MARGINAL OPTIMAL PARTIAL TRANSPORT PROBLEM
• The optimal partial transport problem
• Kantorovich-Rubinstein Norm and Its Application in the Theory of Lipschitz Spaces
• A GEOMETRIC STUDY OF WASSERSTEIN SPACES: ULTRAMETRICS
• Unbalanced optimal transport: dynamic and Kantorovich formulations
• Unnormalized optimal transport
• Convergence of entropic schemes for optimal transport and gradient flows
• Multivariate goodness-of-fit tests based on Wasserstein distance
• Multiscale strategies for computing optimal transport
• The Phylogenetic Kantorovich–Rubinstein Metric for Environmental Sequence Samples
• Imaging with Kantorovich-Rubinstein discrepancy
• Procrustes metrics on covariance operators and optimal transportation of Gaussian processes
• Inference for empirical Wasserstein distances on finite spaces
• Fast Discrete Distribution Clustering Using Wasserstein Barycenter With Sparse Support
• Randomized Wasserstein barycenter computation: resampling with statistical guarantees
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
• Empirical regularized optimal transport: statistical theory and applications
• Optimal transport: fast probabilistic approximation with exact solvers
• Title not available (Why is that?)
• Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)
• A framework for Wasserstein-1-type metrics

Cited In (9)

• On computing medians of marked point process data under edit distance
• ANOVA for metric spaces, with applications to spatial data
• Barycenters in the Hellinger-Kantorovich space
• Computing Wasserstein barycenters via operator splitting: the method of averaged marginals
• Explicit expressions and computational methods for the Fortet-Mourier distance of positive measures to finite weighted sums of Dirac measures
• Nonlinear inverse optimal transport: identifiability of the transport cost from its marginals and optimal values
• Hellinger–Kantorovich barycenter between Dirac measures
• Unbalanced optimal total variation transport problems and generalized Wasserstein barycenters
• Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)

This page was built for publication: Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2096952)