zbMATH — the first resource for mathematics

Wasserstein distance to independence models. (English) Zbl 1460.62205
Summary: An independence model for discrete random variables is a Segre-Veronese variety in a probability simplex. Any metric on the set of joint states of the random variables induces a Wasserstein metric on the probability simplex. The unit ball of this polyhedral norm is dual to the Lipschitz polytope. Given any data distribution, we seek to minimize its Wasserstein distance to a fixed independence model. The solution to this optimization problem is a piecewise algebraic function of the data. We compute this function explicitly in small instances, we study its combinatorial structure and algebraic degrees in general, and we present some experimental case studies.
62R01 Algebraic statistics
60C05 Combinatorial probability
62B05 Sufficient statistics and fields
Macaulay2; SCIP
Full Text: DOI
[1] Bassetti, F.; Bodini, A.; Regazzini, E., On minimum Kantorovich distance estimators, Stat. Probab. Lett., 76, 1298-1302 (2006) · Zbl 1090.62030
[2] Çelik, T. O.; Jamneshan, A.; Montúfar, G.; Sturmfels, B.; Venturello, L., Optimal transport to a variety, (Mathematical Aspects of Computer and Information Sciences. Mathematical Aspects of Computer and Information Sciences, Springer Lecture Notes in Computer Science, vol. 11989 (2020)), 364-381
[3] Cellini, P.; Marietti, M., Root polytopes and Abelian ideals, J. Algebraic Comb., 39, 607-645 (2014) · Zbl 1291.05214
[4] D’Alì, A.; Delucchi, E.; Michałek, M., Many faces of symmetric edge polytopes (2019), Preprint
[5] Draisma, J.; Horobeţ, E.; Ottaviani, G.; Sturmfels, B.; Thomas, R. R., The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16, 99-149 (2016) · Zbl 1370.51020
[6] Galvin, D., On homomorphisms from the Hamming cube to Z, Isr. J. Math., 138, 189-213 (2003) · Zbl 1040.05021
[7] Gawrilow, E.; Joswig, M., : a framework for analyzing convex polytopes, (Polytopes—Combinatorics and Computation. Polytopes—Combinatorics and Computation, Oberwolfach, 1997. Polytopes—Combinatorics and Computation. Polytopes—Combinatorics and Computation, Oberwolfach, 1997, DMV Sem., vol. 29 (2000), Birkhäuser: Birkhäuser Basel), 43-73 · Zbl 0960.68182
[8] Gleixner, A., The SCIP optimization suite 6.0 (2018), Tech report. Optimization online
[9] Gordon, J.; Petrov, F., Combinatorics of the Lipschitz polytope, Arnold Math. J., 3, 205-218 (2017) · Zbl 1386.52010
[10] Grayson, D. R.; Stillman, M. E., Macaulay2, a software system for research in algebraic geometry (2020), Available at
[11] Joswig, M.; Kulas, K., Tropical and ordinary convexity combined, Adv. Geom., 10, 333-352 (2010) · Zbl 1198.14060
[12] Montrucchio, L.; Pistone, G., Kantorovich distance on a finite metric space (2019), Preprint
[13] Nie, J.; Ranestad, K.; Sturmfels, B., The algebraic degree of semidefinite programming, Math. Program., 122, 379-405 (2010) · Zbl 1184.90119
[14] Rostalski, P.; Sturmfels, B., Dualities in convex algebraic geometry, Rend. Mat. Appl. (7), 30, 285-327 (2010) · Zbl 1234.90012
[15] Sodomaco, L., The distance function from the variety of partially symmetric rank-one tensors (2020), Università degli Studi di Firenze, PhD thesis
[16] Tran, N. M., Enumerating polytropes, J. Comb. Theory, Ser. A, 151, 1-22 (2017) · Zbl 1454.14156
[17] Villani, C., Optimal Transport: Old and New, vol. 338 (2008), Springer Science & Business Media · Zbl 1158.53036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.