2019/05/18 by Luigi Montrucchio, Montrucchio, Luigi, Giovanni Pistone +1 · 1 citation
Computer Science · Mathematics · #05C05 #05C12 #05C22 #46B85 #90C08 #90C35 #FOS: Mathematics #Geometric Analysis and Curvature Flows #Point processes and geometric inequalities #Probability (math.PR) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1905.07547
openalex publication_date 2019/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Kantorovich distance (or 1-Wasserstein distance) on the probability simplex of a finite metric space is the value of a Linear Programming problem for which a closed-form expression is known in some cases. When the ground distance is defined by a graph, a few examples have already been studied. In the present paper, after re-deriving, with different tools, the result for trees, we prove that, for an arbitrary weighted graph, the K-distance is the minimum of the K-distances over all the spanning trees associated with the graph. We work in the dual LP-problem by using Arens-Eells norm associated with the metric space. Finally, we introduce new norms that are naturally related to ℓ1-embeddable distances and allows for a partial extension of our results to this new setting.