IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v84y2016i2d10.1007_s00186-016-0549-x.html
   My bibliography  Save this article

Discrete Wasserstein barycenters: optimal transport for discrete data

Author

Listed:
  • Ethan Anderes

    (University of California Davis)

  • Steffen Borgwardt

    (Technische Universität München)

  • Jacob Miller

    (University of California Davis)

Abstract

Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to statistics and computer science. When the marginal probability measures are absolutely continuous (or vanish on small sets) the theory of Wasserstein barycenters is well-developed [see the seminal paper (Agueh and Carlier in SIAM J Math Anal 43(2):904–924, 2011)]. However, exact continuous computation of Wasserstein barycenters in this setting is tractable in only a small number of specialized cases. Moreover, in many applications data is given as a set of probability measures with finite support. In this paper, we develop theoretical results for Wasserstein barycenters in this discrete setting. Our results rely heavily on polyhedral theory which is possible due to the discrete structure of the marginals. The results closely mirror those in the continuous case with a few exceptions. In this discrete setting we establish that Wasserstein barycenters must also be discrete measures and there is always a barycenter which is provably sparse. Moreover, for each Wasserstein barycenter there exists a non-mass-splitting optimal transport to each of the discrete marginals. Such non-mass-splitting transports do not generally exist between two discrete measures unless special mass balance conditions hold. This makes Wasserstein barycenters in this discrete setting special in this regard. We illustrate the results of our discrete barycenter theory with a proof-of-concept computation for a hypothetical transportation problem with multiple marginals: distributing a fixed set of goods when the demand can take on different distributional shapes characterized by the discrete marginal distributions. A Wasserstein barycenter, in this case, represents an optimal distribution of inventory facilities which minimize the squared distance/transportation cost totaled over all demands.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:mathme:v:84:y:2016:i:2:d:10.1007_s00186-016-0549-x
    DOI: 10.1007/s00186-016-0549-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-016-0549-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00186-016-0549-x?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. Pierre-André Chiappori & Robert McCann & Lars Nesheim, 2010. "Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(2), pages 317-354, February.
    2. G. Carlier & I. Ekeland, 2010. "Matching for teams," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(2), pages 397-418, February.
    3. Mathias Beiglbock & Pierre Henry-Labord`ere & Friedrich Penkner, 2011. "Model-independent Bounds for Option Prices: A Mass Transport Approach," Papers 1106.5929, arXiv.org, revised Feb 2013.
    4. Miles Lubin & Iain Dunning, 2015. "Computing in Operations Research Using Julia," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 238-248, May.
    5. A. Galichon & P. Henry-Labord`ere & N. Touzi, 2014. "A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options," Papers 1401.3921, arXiv.org.
    6. repec:dau:papers:123456789/6728 is not listed on IDEAS
    7. Mathias Beiglböck & Pierre Henry-Labordère & Friedrich Penkner, 2013. "Model-independent bounds for option prices—a mass transport approach," Finance and Stochastics, Springer, vol. 17(3), pages 477-501, July.
    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. Steffen Borgwardt & Felix Happach, 2019. "Good Clusterings Have Large Volume," Operations Research, INFORMS, vol. 67(1), pages 215-231, January.
    3. Puccetti, Giovanni & Rüschendorf, Ludger & Vanduffel, Steven, 2020. "On the computation of Wasserstein barycenters," Journal of Multivariate Analysis, Elsevier, vol. 176(C).
    4. 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.
    5. Steffen Borgwardt, 2022. "An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters," Operational Research, Springer, vol. 22(2), pages 1511-1551, April.

    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. Steffen Borgwardt, 2022. "An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters," Operational Research, Springer, vol. 22(2), pages 1511-1551, April.
    2. Julio Backhoff-Veraguas & Gudmund Pammer, 2019. "Stability of martingale optimal transport and weak optimal transport," Papers 1904.04171, arXiv.org, revised Dec 2020.
    3. Daniel Bartl & Michael Kupper & David J. Prömel & Ludovic Tangpi, 2019. "Duality for pathwise superhedging in continuous time," Finance and Stochastics, Springer, vol. 23(3), pages 697-728, July.
    4. Alessandro Doldi & Marco Frittelli, 2023. "Entropy martingale optimal transport and nonlinear pricing–hedging duality," Finance and Stochastics, Springer, vol. 27(2), pages 255-304, April.
    5. Acciaio, B. & Backhoff-Veraguas, J. & Zalashko, A., 2020. "Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization," Stochastic Processes and their Applications, Elsevier, vol. 130(5), pages 2918-2953.
    6. David Hobson & Dominykas Norgilas, 2019. "Robust bounds for the American put," Finance and Stochastics, Springer, vol. 23(2), pages 359-395, April.
    7. Matteo Burzoni & Marco Frittelli & Marco Maggis, 2015. "Model-free Superhedging Duality," Papers 1506.06608, arXiv.org, revised May 2016.
    8. Florian Stebegg, 2014. "Model-Independent Pricing of Asian Options via Optimal Martingale Transport," Papers 1412.1429, arXiv.org.
    9. Lim, Tongseok, 2020. "Optimal martingale transport between radially symmetric marginals in general dimensions," Stochastic Processes and their Applications, Elsevier, vol. 130(4), pages 1897-1912.
    10. Mathias Beiglbock & Alexander M. G. Cox & Martin Huesmann & Nicolas Perkowski & David J. Promel, 2015. "Pathwise super-replication via Vovk's outer measure," Papers 1504.03644, arXiv.org, revised Jul 2016.
    11. Acciaio, Beatrice & Larsson, Martin, 2017. "Semi-static completeness and robust pricing by informed investors," LSE Research Online Documents on Economics 68502, London School of Economics and Political Science, LSE Library.
    12. Ibrahim Ekren & H. Mete Soner, 2016. "Constrained Optimal Transport," Papers 1610.02940, arXiv.org, revised Sep 2017.
    13. Linn Engstrom & Sigrid Kallblad & Johan Karlsson, 2024. "Computation of Robust Option Prices via Structured Multi-Marginal Martingale Optimal Transport," Papers 2406.09959, arXiv.org.
    14. Benjamin Jourdain & Gudmund Pammer, 2023. "An extension of martingale transport and stability in robust finance," Papers 2304.09551, arXiv.org.
    15. Marcel Nutz & Johannes Wiesel, 2024. "On the Martingale Schr\"odinger Bridge between Two Distributions," Papers 2401.05209, arXiv.org.
    16. Erhan Bayraktar & Shuoqing Deng & Dominykas Norgilas, 2023. "Supermartingale Brenier’s Theorem with Full-Marginal Constraint," World Scientific Book Chapters, in: Robert A Jarrow & Dilip B Madan (ed.), Peter Carr Gedenkschrift Research Advances in Mathematical Finance, chapter 17, pages 569-636, World Scientific Publishing Co. Pte. Ltd..
    17. Mathias Beiglbock & Marcel Nutz & Florian Stebegg, 2019. "Fine Properties of the Optimal Skorokhod Embedding Problem," Papers 1903.03887, arXiv.org, revised Apr 2020.
    18. Marcel Nutz & Florian Stebegg, 2016. "Canonical Supermartingale Couplings," Papers 1609.02867, arXiv.org, revised Nov 2017.
    19. David Hobson & Martin Klimmek, 2015. "Robust price bounds for the forward starting straddle," Finance and Stochastics, Springer, vol. 19(1), pages 189-214, January.
    20. Stephan Eckstein & Michael Kupper, 2018. "Computation of optimal transport and related hedging problems via penalization and neural networks," Papers 1802.08539, arXiv.org, revised Jan 2019.

    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:spr:mathme:v:84:y:2016:i:2:d:10.1007_s00186-016-0549-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.