Wasserstein barycenters can be computed in polynomial time in fixed dimension

• URL: http://arxiv.org/abs/2006.08012v2
• Date: Wed, 9 Dec 2020 22:15:32 GMT
• Title: Wasserstein barycenters can be computed in polynomial time in fixed dimension
• Authors: Jason M. Altschuler, Enric Boix-Adsera
• Abstract summary: It is unknown whether Wasserstein barycenters can be computed in time or to high precision. Our approach is to solve an exponential-size linear programming formulation.
• Score: 2.66512000865131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with $\textrm{polylog}(1/\varepsilon)$ runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.

Related papers

• Towards Efficient Time Stepping for Numerical Shape Correspondence [55.2480439325792]
  Methods based on partial differential equations (PDEs) have been established, encompassing e.g. the classic heat kernel signature. We consider here several time stepping schemes. The goal of this investigation is to assess, if one may identify a useful property of methods for time integration for the shape analysis context.
  arXiv  Detail & Related papers  (2023-12-21T13:40:03Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Stability of Entropic Wasserstein Barycenters and application to random geometric graphs [8.7314407902481]
  Wasserstein barycenters (WB) are a notion of barycenters derived from the theory of Optimal Transport. We show how WBs on discretized meshes relate to the geometry of the underlying manifold.
  arXiv  Detail & Related papers  (2022-10-19T13:17:03Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  We give an input sparsity time sampling algorithm for approximating the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time.
  arXiv  Detail & Related papers  (2022-02-09T15:26:03Z)
• Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
  We present an algorithm to approximate the Wasserstein-2 barycenters of continuous measures via a generative model. Based on the celebrity faces dataset, we construct Ave, celeba! dataset which can be used for quantitative evaluation of barycenter algorithms.
  arXiv  Detail & Related papers  (2022-01-28T16:59:47Z)
• Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
  We study dimensionality reduction techniques for the Wasserstein barycenter problem. We show that randomized dimensionality reduction can be used to map the problem to a space of dimension $O(log n)$ independent of both $d$ and $k$. We also provide a coreset construction for the Wasserstein barycenter problem that significantly decreases the number of input distributions.
  arXiv  Detail & Related papers  (2021-10-18T02:57:25Z)
• Fixed Support Tree-Sliced Wasserstein Barycenter [40.087553363884396]
  We propose a barycenter under the tree-Wasserstein distance, called the fixed support tree-Wasserstein barycenter (FS-TWB) and its extension, called the fixed support tree-sliced Wasserstein barycenter (FS-TSWB) We show that the FS-TWB and FS-TSWB can be solved two orders of magnitude faster than the original Wasserstein barycenter.
  arXiv  Detail & Related papers  (2021-09-08T04:50:33Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that mitigates the curse of dimensionality.
  arXiv  Detail & Related papers  (2021-02-05T19:23:35Z)
• Wasserstein barycenters are NP-hard to compute [0.0]
  The problem of computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) has attracted considerable recent attention due to many applications in data science. It is an open question whether this exponential dependence is improvable to a dependence. This paper uncovers a "curse of dimensionality" for computation.
  arXiv  Detail & Related papers  (2021-01-04T17:16:45Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
  arXiv  Detail & Related papers  (2020-02-05T03:09:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.