Kantorovich-Rubinstein distance and barycenter for finitely supported measures: Foundations and Algorithms
Introduces KR distance and barycenter based on unbalanced optimal transport, enabling comparison of measures with different total mass.
Key Findings
Methodology
This work extends unbalanced optimal transport (UOT) by defining the Kantorovich-Rubinstein (KR) distance, incorporating a cost parameter C for mass creation and destruction. The authors analyze the structural properties of KR distance and barycenter, proving support set finiteness and sparsity. They derive a closed-form solution on ultrametric trees, enabling efficient computation. The approach transforms the barycenter problem into a modified OT problem, leveraging existing solvers. Extensive synthetic experiments demonstrate KR barycenters outperform traditional OT barycenters in robustness and structural fidelity, with parameters C controlling multi-scale behavior. The framework is further extended to Gaussian Hellinger-Kantorovich and Wasserstein-Fisher-Rao distances.
Key Results
- On synthetic datasets, KR barycenters show support support points proportional to input measures, with support size linearly bounded. The closed-form solution on ultrametric trees confirms theoretical predictions. Parameter C smoothly interpolates between Wasserstein and total variation metrics, providing multi-scale comparison. In high-dimensional real data, KR distances outperform classical metrics in scenarios with significant mass differences, avoiding normalization issues. Computationally, the method scales efficiently by transforming into standard OT problems, with support for sparse solutions.
- Experimental results reveal that KR barycenters maintain structural features better than Wasserstein barycenters, especially when measures differ significantly in total mass. The support set analysis shows sparsity and explicit structure, facilitating interpretability. The parameter C effectively tunes the scale, with larger C capturing global differences and smaller C focusing on local variations. The approach demonstrates robustness across diverse synthetic and real-world datasets, with computational times comparable to existing OT algorithms.
- The theoretical derivation of a closed-form solution on ultrametric trees provides deep geometric insights, enabling fast computation and support set characterization. The existence of sparse barycenters with bounded support supports large-scale applications. The framework opens avenues for integrating prior knowledge via parameter C, and for developing adaptive algorithms that tune C dynamically, promising further improvements in efficiency and accuracy.
Significance
This research advances the theoretical foundation of non-balanced measures comparison, overcoming the limitations of classical Wasserstein distances. By allowing mass creation and destruction, the KR distance models real-world scenarios more faithfully, such as biological data with varying intensities or economic measures with fluctuating totals. The explicit support structure and closed-form solutions on ultrametric trees facilitate scalable algorithms, making the approach suitable for high-dimensional, large-scale applications. The framework enriches the toolkit for statistical inference, machine learning, and bioinformatics, enabling more flexible and interpretable analysis of non-conservative data. Its ability to interpolate between local and global differences addresses a long-standing challenge in measure comparison, promising broad impact across disciplines.
Technical Contribution
The core technical innovation lies in defining a parameterized unbalanced distance (KR) that interpolates between Wasserstein and total variation metrics, with a clear geometric interpretation. The authors prove the existence of finite, sparse barycenters, and derive a closed-form solution on ultrametric trees, leveraging the tree's hierarchical structure. They reformulate the barycenter problem as a modified OT problem, compatible with standard solvers, and analyze the distance's metric properties, including bounds and parameter influence. The support set analysis provides explicit support bounds, enabling scalable algorithms. The extension to Gaussian Hellinger-Kantorovich and Wasserstein-Fisher-Rao distances broadens the framework's applicability, offering new theoretical guarantees and computational strategies.
Novelty
This work is the first systematic development of the KR distance, a flexible unbalanced measure with a tunable parameter C, bridging the gap between classical OT and total variation. Unlike prior approaches relying solely on normalization or entropy regularization, KR explicitly models mass creation/destruction, with a clear geometric and support structure analysis. The derivation of a closed-form solution on ultrametric trees is novel, providing computational efficiency and theoretical clarity. The support and sparsity results for barycenters extend known properties from Wasserstein to unbalanced measures, offering new insights into measure aggregation under non-conservative conditions.
Limitations
- Parameter C selection remains heuristic, lacking adaptive schemes, which can affect performance in diverse datasets. The closed-form solution applies mainly to ultrametric trees, limiting generalization to arbitrary metric spaces. Computational complexity still grows with support size, especially in high dimensions. The current framework assumes discrete measures; continuous extensions are non-trivial and require further research.
Future Work
Future directions include developing data-driven methods for adaptive C selection, extending the closed-form solutions to more general metric spaces, and integrating deep learning techniques for large-scale optimization. Exploring continuous measure extensions and applications in dynamic settings, such as time-evolving data, are promising avenues. Additionally, combining KR distances with probabilistic models could enhance interpretability and robustness, broadening their use in complex real-world scenarios.
AI Executive Summary
Deep Dive
Plain Language Accessible to non-experts
想象你在厨房做饭。每种食材代表一种测度，数量代表它的“重量”。有时候，你需要用不同的食材组合来做一道菜，但每次用的食材总量可能不同。传统的方法就像把所有食材都调成一样的量，但这样会失去原本的味道。现在，这个新方法就像厨师可以根据需要，灵活地增加或减少某些食材，同时考虑到成本和时间。这样，不仅能保持菜的原味，还能根据不同的需求调整。它让我们在比较不同菜谱时，更加自然和真实，不会因为强制统一而失去重要信息。
ELI14 Explained like you're 14
想象你和朋友们在玩拼图游戏。每个人手里都有一块拼图，但大小和形状都不一样。有时候，你们想拼出一幅完整的画，但不能简单地把所有拼图都裁成一样大。以前的方法是把所有拼图都裁成一样大小，但会丢失一些特色。现在，有一种新方法，就像你们可以灵活调整拼图的大小和位置，既保持每块拼图的特色，又能拼出完整的画面。这让拼图变得更灵活，也更贴近真实情况。它就像给拼图游戏加入了魔法，让大家都能找到最合适的拼法，不再拘泥于统一的规则。
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.