English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Computationally solving multi-marginal optimal transport (MOT) with squaredEuclidean costs for $N$ discrete probability measures has recently attractedconsiderable attention, in part because of the correspondence of its solutionswith Wasserstein-$2$ barycenters, which have many applications in data science.In general, this problem is NP-hard, calling for practical approximativealgorithms. While entropic regularization has been successfully applied toapproximate Wasserstein barycenters, this loses the sparsity of the optimalsolution, making it difficult to solve the MOT problem directly in practicebecause of the curse of dimensionality. Thus, for obtaining barycenters, oneusually resorts to fixed-support restrictions to a grid, which is, however,prohibitive in higher ambient dimensions $d$. In this paper, after analyzingthe relationship between MOT and barycenters, we present two algorithms toapproximate the solution of MOT directly, requiring mainly just $N-1$ standardtwo-marginal OT computations. Thus, they are fast, memory-efficient and easy toimplement and can be used with any sparse OT solver as a black box. Moreover,they produce sparse solutions and show promising numerical results. We analyzethese algorithms theoretically, proving upper and lower bounds for the relativeapproximation error.

Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters