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

DOI10.1007/S00245-022-09911-XMaRDI QIDQ2096952zbMATH OpenOpenAlexFDO

Authors Florian Heinemann, Marcel Klatt, Axel Munk

Publication date 11 November 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)