IDEAS home Printed from https://ideas.repec.org/a/eee/jmvana/v176y2020ics0047259x19302544.html
   My bibliography  Save this article

On the computation of Wasserstein barycenters

Author

Listed:
  • Puccetti, Giovanni
  • Rüschendorf, Ludger
  • Vanduffel, Steven

Abstract

The Wasserstein barycenter is an important notion in the analysis of high dimensional data with a broad range of applications in applied probability, economics, statistics, and in particular to clustering and image processing. In this paper, we state a general version of the equivalence of the Wasserstein barycenter problem to the n-coupling problem. As a consequence, the coupling to the sum principle (characterizing solutions to the n-coupling problem) provides a novel criterion for the explicit characterization of barycenters. Based on this criterion, we provide as a main contribution the simple to implement iterative swapping algorithm (ISA) for computing barycenters. The ISA is a completely non-parametric algorithm which provides a sharp image of the support of the barycenter and has a quadratic time complexity which is comparable to other well established algorithms designed to compute barycenters. The algorithm can also be applied to more complex optimization problems like the k-barycenter problem.

Suggested Citation

  • Puccetti, Giovanni & Rüschendorf, Ludger & Vanduffel, Steven, 2020. "On the computation of Wasserstein barycenters," Journal of Multivariate Analysis, Elsevier, vol. 176(C).
    • Handle: RePEc:eee:jmvana:v:176:y:2020:i:c:s0047259x19302544
    DOI: 10.1016/j.jmva.2019.104581
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0047259X19302544
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jmva.2019.104581?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dowson, D. C. & Landau, B. V., 1982. "The Fréchet distance between multivariate normal distributions," Journal of Multivariate Analysis, Elsevier, vol. 12(3), pages 450-455, September.
    2. Rüschendorf, Ludger & Uckelmann, Ludger, 2002. "On the n-Coupling Problem," Journal of Multivariate Analysis, Elsevier, vol. 81(2), pages 242-258, May.
    3. Rüschendorf, L. & Rachev, S. T., 1990. "A characterization of random variables with minimum L2-distance," Journal of Multivariate Analysis, Elsevier, vol. 32(1), pages 48-54, January.
    4. Ethan Anderes & Steffen Borgwardt & Jacob Miller, 2016. "Discrete Wasserstein barycenters: optimal transport for discrete data," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(2), pages 389-409, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Johannes von Lindheim, 2023. "Simple approximative algorithms for free-support Wasserstein barycenters," Computational Optimization and Applications, Springer, vol. 85(1), pages 213-246, May.
    2. Alessia Benevento & Fabrizio Durante, 2023. "Wasserstein Dissimilarity for Copula-Based Clustering of Time Series with Spatial Information," Mathematics, MDPI, vol. 12(1), pages 1-15, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rippl, Thomas & Munk, Axel & Sturm, Anja, 2016. "Limit laws of the empirical Wasserstein distance: Gaussian distributions," Journal of Multivariate Analysis, Elsevier, vol. 151(C), pages 90-109.
    2. Valentina Masarotto & Victor M. Panaretos & Yoav Zemel, 2019. "Procrustes Metrics on Covariance Operators and Optimal Transportation of Gaussian Processes," Sankhya A: The Indian Journal of Statistics, Springer;Indian Statistical Institute, vol. 81(1), pages 172-213, February.
    3. Elham Yousefi & Luc Pronzato & Markus Hainy & Werner G. Müller & Henry P. Wynn, 2023. "Discrimination between Gaussian process models: active learning and static constructions," Statistical Papers, Springer, vol. 64(4), pages 1275-1304, August.
    4. Faugeras, Olivier P. & Rüschendorf, Ludger, 2021. "Functional, randomized and smoothed multivariate quantile regions," Journal of Multivariate Analysis, Elsevier, vol. 186(C).
    5. Rüschendorf, Ludger, 1996. "On c-optimal random variables," Statistics & Probability Letters, Elsevier, vol. 27(3), pages 267-270, April.
    6. Knott, Martin & Smith, Cyril, 2006. "Choosing joint distributions so that the variance of the sum is small," Journal of Multivariate Analysis, Elsevier, vol. 97(8), pages 1757-1765, September.
    7. Jan Bergenthum & Ludger Rüschendorf, 2006. "Comparison of Option Prices in Semimartingale Models," Finance and Stochastics, Springer, vol. 10(2), pages 222-249, April.
    8. Steffen Borgwardt & Stephan Patterson, 2021. "On the computational complexity of finding a sparse Wasserstein barycenter," Journal of Combinatorial Optimization, Springer, vol. 41(3), pages 736-761, April.
    9. Ludger Rüschendorf, 2012. "Worst case portfolio vectors and diversification effects," Finance and Stochastics, Springer, vol. 16(1), pages 155-175, January.
    10. Bernard, Carole & Chen, Jinghui & Rüschendorf, Ludger & Vanduffel, Steven, 2023. "Coskewness under dependence uncertainty," Statistics & Probability Letters, Elsevier, vol. 199(C).
    11. Zhongzhi Lawrence He, 2018. "Comparing Asset Pricing Models: Distance-based Metrics and Bayesian Interpretations," Papers 1803.01389, arXiv.org.
    12. Alfred Galichon & Damien Bosc, 2010. "Extreme dependence for multivariate data," Working Papers hal-03588294, HAL.
    13. Mordant, Gilles & Segers, Johan, 2022. "Measuring dependence between random vectors via optimal transport," Journal of Multivariate Analysis, Elsevier, vol. 189(C).
    14. Rüschendorf, Ludger & Uckelmann, Ludger, 2002. "On the n-Coupling Problem," Journal of Multivariate Analysis, Elsevier, vol. 81(2), pages 242-258, May.
    15. Whiteley, Nick, 2021. "Dimension-free Wasserstein contraction of nonlinear filters," Stochastic Processes and their Applications, Elsevier, vol. 135(C), pages 31-50.
    16. Henri Heinich, 2006. "The Monge Problem in Banach Spaces," Journal of Theoretical Probability, Springer, vol. 19(2), pages 509-534, June.
    17. Tomonari Sei, 2011. "Gradient modeling for multivariate quantitative data," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 63(4), pages 675-688, August.
    18. Steffen Borgwardt & Felix Happach, 2019. "Good Clusterings Have Large Volume," Operations Research, INFORMS, vol. 67(1), pages 215-231, January.
    19. Alfred Galichon & Damien Bosc, 2010. "Extreme dependence for multivariate data," SciencePo Working papers hal-03588294, HAL.
    20. Ledoit, Olivier & Wolf, Michael, 2021. "Shrinkage estimation of large covariance matrices: Keep it simple, statistician?," Journal of Multivariate Analysis, Elsevier, vol. 186(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jmvana:v:176:y:2020:i:c:s0047259x19302544. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/622892/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.