An Integer Program for Pricing Support Points of Exact Barycenters

References

• Agueh M, Carlier G (2011) Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43(2):904–924.Google Scholar
• Altschuler J, Boix-Adserà E (2021) Wasserstein barycenters can be computed in polynomial time in fixed dimension. J. Machine Learn. Res. 22:1–19.Google Scholar
• Altschuler J, Boix-Adserà E (2022) Wasserstein barycenters are NP-hard to compute. SIAM J. Math. Data Sci. 4(1):179–203.Google Scholar
• Anderes E, Borgwardt S, Miller J (2016) Discrete Wasserstein barycenters: Optimal transport for discrete data. Math. Methods Oper. Res. 84(2):389–409.Google Scholar
• Beiglböck M, Henry-Labordere P, Penkner F (2013) Model-independent bounds for option prices: A mass transport approach. Finance Stochastics 17(3):477–501.Google Scholar
• Benamou JD, Carlier G, Nenna L (2016) A numerical method to solve multi-marginal optimal transport problems with Coulomb cost. Glowinski R, Osher S, Yin W, eds. Splitting Methods in Communication, Imaging, Science, and Engineering (Springer, Cham, Switzerland), 577–601.Google Scholar
• Benamou JD, Carlier G, Nenna L (2019) Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm. Numerical Math. 142:33–54.Google Scholar
• Benamou JD, Carlier G, Cuturi M, Nenna L, Peyré G (2015) Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37(2):A1111–A1138.Google Scholar
• Borgwardt S (2022) An LP-based, strongly polynomial 2-approximation algorithm for sparse Wasserstein barycenters. Oper. Res. 22:1511–1551.Google Scholar
• Borgwardt S, Patterson S (2020) Improved linear programs for discrete barycenters. INFORMS J. Optim. 2:14–33.Link, Google Scholar
• Borgwardt S, Patterson S (2021) On the computational complexity of finding a sparse Wasserstein barycenter. J. Combinatorial Optim. 41:736–761.Google Scholar
• Borgwardt S, Patterson S (2022) A column generation approach to the discrete barycenter problem. Discrete Optim. 43:100674.Google Scholar
• Borgwardt S, Brieden A, Gritzmann P (2011) Constrained minimum-k-star clustering and its application to the consolidation of farmland. Oper. Res. 11(1):1–17.Google Scholar
• Carlier G, Ekeland I (2010) Matching for teams. Econom. Theory 42(2):397–418.Google Scholar
• Carlier G, Oberman A, Oudet E (2015) Numerical methods for matching for teams and Wasserstein barycenters. ESAIM Math. Modeling Numerical Anal. 49(6):1621–1642.Google Scholar
• Chiaporri PA, McCann R, Nesheim L (2010) Hedonic price equilibria, stable matching and optimal transport: Equivalence, topology and uniqueness. Econom. Theory 42(2):317–354.Google Scholar
• Cohen S, Arbel M, Deisenroth MP (2020) Estimating barycenters of measures in high dimensions. Preprint, submitted July 14, https://arxiv.org/abs/2007.07105.Google Scholar
• Cotar C, Friesecke G, Klüppelberg C (2013) Density functional theory and optimal transportation with Coulomb cost. Comm. Pure Appl. Math. 66(4):548–599.Google Scholar
• Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal tansportation distances. Adv. Neural Inform. Processing Systems 26:2292–2300.Google Scholar
• Cuturi M, Doucet A (2014) Fast computation of Wasserstein barycenters. Xing EP, Jebara T, eds. Proc. 31st Internat. Conf. on Machine Learn. (JMLR.org), 685–693.Google Scholar
• Haasler I, Singh R, Zhang Q, Karlsson J, Chen Y (2021) Multi-marginal optimal transport and probabilistic graphical models. IEEE Trans. Inform. Theory 67(7):4647–4668.Google Scholar
• Heitz M, Bonneel N, Coeurjolly D, Cuturi M, Peyré G (2021) Ground metric learning on graphs. J. Math. Imaging Vision 63:89–107.Google Scholar
• Ho N, Huynh V, Phung D, Jordan M (2019) Probabilistic multilevel clustering via composite transportation distance. Chaudhuri K, Sugiyama M, eds. Proc. 22nd Internat. Conf. on Artificial Intelligence and Statist., vol. 89 (PMLR, New York), 3149–3157.Google Scholar
• Ho N, Nguyen XL, Yurochkin M, Bui HH, Huynh V, Phung D (2017) Multilevel clustering via Wasserstein means. Precup D, Teh YW, eds. Proc. Internat. Conf. on Machine Learn., vol. 70 (PMLR, New York), 1501–1509.Google Scholar
• Jain A, Zhong Y, Dubuisson-Jolly MP (1998) Deformable template models: A review. Signal Processing 71(2):109–129.Google Scholar
• Janati H, Cuturi M, Gramfort A (2020b) Debiased Sinkhorn barycenters. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. on Machine Learn., vol. 119 (PMLR, New York), 4692–4701.Google Scholar
• Janati H, Bazeille T, Thirion B, Cuturi M, Gramfort A (2020a) Multi-subject MEG/EEG source imaging with sparse multi-task regression. Neuroimage 220:116847.Google Scholar
• Kroshnin A, Tupitsa N, Dvinskikh D, Dvurechensky P, Gasnikov A, Uribe C (2019) On the complexity of approximating Wasserstein barycenters. Chaudhuri K, Salakhutdinov R, eds. Proc. Internat. Conf. on Machine Learn., vol. 97 (PMLR, New York), 3530–3540.Google Scholar
• Lin T, Ho N, Cuturi M, Jordan M (2020) Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm. Adv. Neural Inform. Processing Systems 33:5368–5380.Google Scholar
• Luise G, Salzo S, Pontil M, Ciliberto C (2019) Sinkhorn barycenters with free support via Frank-Wolfe algorithm. Adv. Neural Inform. Processing Systems 32:9322–9333.Google Scholar
• Munch E, Turner K, Bendich P, Mukherjee S, Mattingly J, Harer J (2015) Probabilistic Fréchet means for time varying persistence diagrams. Electronic J. Statist. 9:1173–1204.Google Scholar
• Natarajan K (2021) Optimization with Marginals and Moments (Dynamic Ideas, Waltham, MA).Google Scholar
• Nenna L (2016) Numerical methods for multi-marginal optimal transportation. PhD thesis, Université Paris-Dauphine, Paris.Google Scholar
• Panaretos V, Zemel Y (2019) Statistical aspects of Wasserstein distances. Annu. Rev. Statist. Appl. 6(1):405–431.Google Scholar
• Peyré G, Cuturi M (2019) Computational optimal transport. Foundations Trends Machine Learn. 11(5–6):355–607.Google Scholar
• Schmitz M, Heitz M, Bonneel N, Ngolé F, Coeurjolly D, Cuturi M, Peyré G, et al. (2018) Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning. SIAM J. Imaging Sci. 11(1):643–678.Google Scholar
• Shen Z, Wang Z, Riebeiro A, Hassani H (2020) Sinkhorn barycenters via functional gradient descent. Adv. Neural Inform. Processing Systems 33:986–996.Google Scholar
• Simon D, Aberdam A (2020) Barycenters of natural images: Constrained Wasserstein barycenters for image morphing. Proc. IEEE/CVF Conf. on Computer Vision and Pattern Recognition (IEEE, Piscataway, NJ), 7907–7916.Google Scholar
• Singh SP, Hug A, Dieuleveut A, Jaggi M (2020) Context mover’s distance & barycenters: Optimal transport of contexts for building representations. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. on Artificial Intelligence and Statist., vol. 108 (PMLR, New York), 3437–3449.Google Scholar
• Solomon J, De Goes F, Peyré G, Cuturi M, Butscher A, Nguyen A, Du T, et al. (2015) Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graphics 34:1–11.Google Scholar
• Trouvé A, Younes L (2005) Local geometry of deformable templates. SIAM J. Math. Anal. 37(1):17–59.Google Scholar
• Villani C (2009) Optimal Transport: Old and New, vol. 338 (Springer-Verlag, Berlin).Google Scholar
• Xu H, Wang W, Liu W, Carin L (2018) Distilled Wasserstein learning for word embedding and topic modeling. Adv. Neural Inform. Processing Systems 32:1723–1732.Google Scholar
• Yan Y, Duffner S, Phutane P, Berthelier A, Blanc C, Garcia C, Chateau T (2021) 2D Wasserstein loss for robust facial landmark detection. Pattern Recognition 116(C):107945.Google Scholar
• Ye J, Li Y, Wu Z, Wang JZ, Li W, Li J (2017) Determining gains acquired from word embedding quantitatively using discrete distribution clustering. Barzilay R, Kan M-Y, eds. Proc. 55th Annual Meeting Assoc. for Comput. Linguistics (Association for Computational Linguistics, New York), 1847–1856.Google Scholar
• Zemel Y, Panaretos VM (2019) Fréchet means and Procrustes analysis in Wasserstein space. Bernoulli 25(2):932–976.Google Scholar