Kantorovich-Rubinstein distance and barycenter for finitely supported measures: Foundations and Algorithms

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 measures by allowing for mass creation and destruction modeled by some cost parameter. We refer to them as Kantorovich-Rubinstein (KR) barycenter and distance. We restrict our analysis to finite ground spaces as demanded for any KR based real world data analysis. 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 KR barycenters of finitely supported measures turns out to be finite and its geometry to be explicitly specified by the support of the input data 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 data sets. We also consider barycenters based on the recently introduced Gaussian Hellinger-Kantorovich and Wasserstein-Fisher-Rao distances.