Dimensionality Reduction for Wasserstein Barycenter
- URL: http://arxiv.org/abs/2110.08991v2
- Date: Tue, 19 Oct 2021 01:10:17 GMT
- Title: Dimensionality Reduction for Wasserstein Barycenter
- Authors: Zachary Izzo, Sandeep Silwal, Samson Zhou
- Abstract summary: 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.
- Score: 6.327655795051619
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Wasserstein barycenter is a geometric construct which captures the notion
of centrality among probability distributions, and which has found many
applications in machine learning. However, most algorithms for finding even an
approximate barycenter suffer an exponential dependence on the dimension $d$ of
the underlying space of the distributions. In order to cope with this "curse of
dimensionality," we study dimensionality reduction techniques for the
Wasserstein barycenter problem. When the barycenter is restricted to support of
size $n$, 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$, and that \emph{any} solution found in the reduced dimension will have its
cost preserved up to arbitrary small error in the original space. We provide
matching upper and lower bounds on the size of the reduced dimension, showing
that our methods are optimal up to constant factors. We also provide a coreset
construction for the Wasserstein barycenter problem that significantly
decreases the number of input distributions. The coresets can be used in
conjunction with random projections and thus further improve computation time.
Lastly, our experimental results validate the speedup provided by
dimensionality reduction while maintaining solution quality.
Related papers
- Max-sliced Wasserstein concentration and uniform ratio bounds of empirical measures on RKHS [9.783697404304025]
Optimal transport and the Wasserstein distance $mathcalW_p$ have recently seen a number of applications in the fields of statistics, machine learning, data science, and the physical sciences.
These applications are however severely restricted by the curse of dimensionality, meaning that the number of data points needed to estimate these problems accurately increases exponentially in the dimension.
We focus here on one of these variants, namely the max-sliced Wasserstein metric $overlinemathcalW_p$.
arXiv Detail & Related papers (2024-05-21T18:47:43Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
We propose a new scalable approach for solving the Wasserstein barycenter problem.
Our methodology is based on the recent Neural OT solver.
We also establish theoretical error bounds for our proposed approach.
arXiv Detail & Related papers (2024-02-06T09:17:07Z) - Krylov Cubic Regularized Newton: A Subspace Second-Order Method with
Dimension-Free Convergence Rate [83.3933097134767]
We introduce a novel subspace cubic regularized Newton method that achieves a dimension-independent global convergence rate of $Oleft(frac1mk+frac1k2right)$.
Our method converges faster than existing random subspace methods, especially for high-dimensional problems.
arXiv Detail & Related papers (2024-01-05T20:24:18Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems.
We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
arXiv Detail & Related papers (2023-02-03T03:19:14Z) - 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) - Randomized Dimensionality Reduction for Facility Location and
Single-Linkage Clustering [13.208510864854894]
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems.
We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem.
arXiv Detail & Related papers (2021-07-05T05:55:26Z) - 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) - Continuous Wasserstein-2 Barycenter Estimation without Minimax
Optimization [94.18714844247766]
Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport.
We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
arXiv Detail & Related papers (2021-02-02T21:01:13Z) - 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) - Sinkhorn Barycenter via Functional Gradient Descent [125.89871274202439]
We consider the problem of computing the barycenter of a set of probability distributions under the Sinkhorn divergence.
This problem has recently found applications across various domains, including graphics, learning, and vision.
We develop a novel functional gradient descent method named Sinkhorn Descent.
arXiv Detail & Related papers (2020-07-20T20:16:47Z) - On a minimum enclosing ball of a collection of linear subspaces [16.466372560527827]
This paper concerns the minimax center of a collection of linear subspaces.
We propose and solve an optimization problem parametrized by the rank of the minimax center.
By scaling the objective and penalizing the information lost by the rank-$k$ minimax center, we jointly recover an optimal dimension, $k*$, and a central subspace, $U* in$ Gr$(k*,n)$ at the center of the minimum enclosing ball, that best represents the data.
arXiv Detail & Related papers (2020-03-27T15:00:49Z)
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.