Theoretical Guarantees for Bridging Metric Measure Embedding and Optimal Transport

• URL: http://arxiv.org/abs/2002.08314v5
• Date: Thu, 22 Apr 2021 17:43:40 GMT
• Title: Theoretical Guarantees for Bridging Metric Measure Embedding and Optimal Transport
• Authors: Mokhtar Z. Alaya, Maxime B\'erar, Gilles Gasso, Alain Rakotomamonjy
• Abstract summary: We consider a method allowing to embed the metric measure spaces in a common Euclidean space and compute an optimal transport (OT) on the embedded distributions. This leads to what we call a sub-embedding robust Wasserstein (SERW) distance.
• Score: 18.61019008000831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel approach for comparing distributions whose supports do not necessarily lie on the same metric space. Unlike Gromov-Wasserstein (GW) distance which compares pairwise distances of elements from each distribution, we consider a method allowing to embed the metric measure spaces in a common Euclidean space and compute an optimal transport (OT) on the embedded distributions. This leads to what we call a sub-embedding robust Wasserstein (SERW) distance. Under some conditions, SERW is a distance that considers an OT distance of the (low-distorted) embedded distributions using a common metric. In addition to this novel proposal that generalizes several recent OT works, our contributions stand on several theoretical analyses: (i) we characterize the embedding spaces to define SERW distance for distribution alignment; (ii) we prove that SERW mimics almost the same properties of GW distance, and we give a cost relation between GW and SERW. The paper also provides some numerical illustrations of how SERW behaves on matching problems.

Related papers

• Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
  The Gromov-Wasserstein (GW) distances define a family of metrics, based on ideas from optimal transport. GW distances are inherently sensitive to outlier noise and cannot accommodate partial matching. We show that our new distances define true metrics, that they induce the same topology as the GW distances, and that they enjoy additional robustness to perturbations.
  arXiv  Detail & Related papers  (2024-11-04T15:53:45Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Characterizing how 'distributional' NLP corpora distance metrics are [2.4921910293793412]
  We describe an abstract quality, called distributionality', of such metrics. A non-distributional metric tends to use very local measurements. A more distributional metric will, in contrast, better capture the distributions' overall distance.
  arXiv  Detail & Related papers  (2023-10-23T11:48:23Z)
• Energy-Based Sliced Wasserstein Distance [47.18652387199418]
  A key component of the sliced Wasserstein (SW) distance is the slicing distribution. We propose to design the slicing distribution as an energy-based distribution that is parameter-free. We then derive a novel sliced Wasserstein metric, energy-based sliced Waserstein (EBSW) distance.
  arXiv  Detail & Related papers  (2023-04-26T14:28:45Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  We introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We compare distances with previous SW variants in various applications such as flows, color transfer, and deep generative modeling to demonstrate the favorable performance of MSW.
  arXiv  Detail & Related papers  (2023-01-10T01:58:15Z)
• Distributional Sliced Embedding Discrepancy for Incomparable Distributions [22.615156512223766]
  Gromov-Wasserstein (GW) distance is a key tool for manifold learning and cross-domain learning. We propose a novel approach for comparing two computation distributions, that hinges on the idea of distributional slicing, embeddings, and on computing the closed-form Wasserstein distance between the sliced distributions.
  arXiv  Detail & Related papers  (2021-06-04T15:11:30Z)
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation [0.0]
  Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric spaces is the metric measureGro-Wasserstein (GW) distance of which is a quadratic. The GW formulation alleviates the comparison of metric spaces equipped with arbitrary positive measures up to isometries.
  arXiv  Detail & Related papers  (2020-09-09T12:38:14Z)
• Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations [79.23797234241471]
  Discriminating between distributions is an important problem in a number of scientific fields. The Linear Optimal Transportation (LOT) embeds the space of distributions into an $L2$-space. We demonstrate the benefits of LOT on a number of distribution classification problems.
  arXiv  Detail & Related papers  (2020-08-20T19:09:33Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• 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.