IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v22y2022i2d10.1007_s12351-020-00589-z.html
   My bibliography  Save this article

An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters

Author

Listed:
  • Steffen Borgwardt

    (University of Colorado Denver)

Abstract

Discrete Wasserstein barycenters correspond to optimal solutions of transportation problems for a set of probability measures with finite support. Discrete barycenters are measures with finite support themselves and exhibit two favorable properties: there always exists one with a provably sparse support, and any optimal transport to the input measures is non-mass splitting. It is open whether a discrete barycenter can be computed in polynomial time. It is possible to find an exact barycenter through linear programming, but these programs may scale exponentially. In this paper, we prove that there is a strongly-polynomial 2-approximation algorithm based on linear programming. First, we show that an exact computation over the union of supports of the input measures gives a tight 2-approximation. This computation can be done through a linear program with setup and solution in strongly-polynomial time. The resulting measure is sparse, but an optimal transport may split mass. We then devise a second, strongly-polynomial algorithm to improve this measure to one with a non-mass splitting transport of lower cost. The key step is an update of the possible support set to resolve mass split. Finally, we devise an iterative scheme that alternates between these two algorithms. The algorithm terminates with a 2-approximation that has both a sparse support and an associated non-mass splitting optimal transport. We conclude with some sample computations and an analysis of the scaling of our algorithms, exhibiting vast improvements in running time over exact LP-based computations and low practical errors.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:operea:v:22:y:2022:i:2:d:10.1007_s12351-020-00589-z
    DOI: 10.1007/s12351-020-00589-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-020-00589-z
    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/s12351-020-00589-z?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. Sébastien Gadat & Ioana Gavra & Laurent Risser, 2018. "How to Calculate the Barycenter of a Weighted Graph," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1085-1118, November.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    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.
    8. 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.
    9. Miles Lubin & Iain Dunning, 2015. "Computing in Operations Research Using Julia," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 238-248, May.
    10. repec:dau:papers:123456789/6728 is not listed on IDEAS
    Full references (including those not matched with items on IDEAS)

    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. 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.
    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:operea:v:22:y:2022:i:2:d:10.1007_s12351-020-00589-z. 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.