Distance-Based Tree-Sliced Wasserstein Distance

• URL: http://arxiv.org/abs/2503.11050v1
• Date: Fri, 14 Mar 2025 03:36:44 GMT
• Title: Distance-Based Tree-Sliced Wasserstein Distance
• Authors: Hoang V. Tran, Khoi N. M. Nguyen, Trang Pham, Thanh T. Chu, Tam Le, Tan M. Nguyen,
• Abstract summary: We propose a novel class of splitting maps that generalizes the existing one studied in Tree-Sliced Wasserstein distance on Systems of Lines.<n>We show that Db-TSW significantly improves accuracy compared to recent SW variants while maintaining low computational cost.
• Score: 6.967581304933985
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To overcome computational challenges of Optimal Transport (OT), several variants of Sliced Wasserstein (SW) has been developed in the literature. These approaches exploit the closed-form expression of the univariate OT by projecting measures onto (one-dimensional) lines. However, projecting measures onto low-dimensional spaces can lead to a loss of topological information. Tree-Sliced Wasserstein distance on Systems of Lines (TSW-SL) has emerged as a promising alternative that replaces these lines with a more advanced structure called tree systems. The tree structures enhance the ability to capture topological information of the metric while preserving computational efficiency. However, at the core of TSW-SL, the splitting maps, which serve as the mechanism for pushing forward measures onto tree systems, focus solely on the position of the measure supports while disregarding the projecting domains. Moreover, the specific splitting map used in TSW-SL leads to a metric that is not invariant under Euclidean transformations, a typically expected property for OT on Euclidean space. In this work, we propose a novel class of splitting maps that generalizes the existing one studied in TSW-SL enabling the use of all positional information from input measures, resulting in a novel Distance-based Tree-Sliced Wasserstein (Db-TSW) distance. In addition, we introduce a simple tree sampling process better suited for Db-TSW, leading to an efficient GPU-friendly implementation for tree systems, similar to the original SW. We also provide a comprehensive theoretical analysis of proposed class of splitting maps to verify the injectivity of the corresponding Radon Transform, and demonstrate that Db-TSW is an Euclidean invariant metric. We empirically show that Db-TSW significantly improves accuracy compared to recent SW variants while maintaining low computational cost via a wide range of experiments.

Related papers

• Spherical Tree-Sliced Wasserstein Distance [6.967581304933985]
  We present an adaptation of tree systems on OT problems for measures supported on a sphere.<n>We obtain an efficient metric for measures on the sphere, named Spherical Tree-Sliced Wasserstein (STSW) distance.
  arXiv  Detail & Related papers  (2025-03-14T10:00:13Z)
• Tree-Sliced Wasserstein Distance on a System of Lines [7.382959387042827]
  We propose the Tree-Sliced Wasserstein distance on a System of Lines (TSW-SL), which brings a connection between SW and TSW. In TSW-SL, we use a variant of the Radon Transform to project measures onto a system of lines, resulting in measures on a space with a tree metric, then leverage TW to efficiently compute distances between them.
  arXiv  Detail & Related papers  (2024-06-19T17:40:11Z)
• Optimal Transport for Measures with Noisy Tree Metric [29.950797721275574]
  We study optimal transport problem for probability measures supported on a tree metric space. In general, this approach is hard to compute, even for measures supported in one space. We show that the robust OT satisfies the metric property and is negative definite.
  arXiv  Detail & Related papers  (2023-10-20T16:56:08Z)
• 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)
• 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)
• GeONet: a neural operator for learning the Wasserstein geodesic [13.468026138183623]
  We present GeONet, a mesh-invariant deep neural operator network that learns the non-linear mapping from the input pair of initial and terminal distributions to the Wasserstein geodesic connecting the two endpoint distributions. We demonstrate that GeONet achieves comparable testing accuracy to the standard OT solvers on simulation examples and the MNIST dataset with considerably reduced inference-stage computational cost by orders of magnitude.
  arXiv  Detail & Related papers  (2022-09-28T21:55:40Z)
• Hierarchical Sliced Wasserstein Distance [27.12983497199479]
  Sliced Wasserstein (SW) distance can be scaled to a large number of supports without suffering from the curse of dimensionality. Despite its efficiency in the number of supports, estimating the sliced Wasserstein requires a relatively large number of projections in high-dimensional settings. We propose to derive projections by linearly and randomly combining a smaller number of projections which are named bottleneck projections. We then formulate the approach into a new metric between measures, named Hierarchical Sliced Wasserstein (HSW) distance.
  arXiv  Detail & Related papers  (2022-09-27T17:46:15Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• CodeVIO: Visual-Inertial Odometry with Learned Optimizable Dense Depth [83.77839773394106]
  We present a lightweight, tightly-coupled deep depth network and visual-inertial odometry system. We provide the network with previously marginalized sparse features from VIO to increase the accuracy of initial depth prediction. We show that it can run in real-time with single-thread execution while utilizing GPU acceleration only for the network and code Jacobian.
  arXiv  Detail & Related papers  (2020-12-18T09:42:54Z)
• 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)
• Augmented Sliced Wasserstein Distances [55.028065567756066]
  We propose a new family of distance metrics, called augmented sliced Wasserstein distances (ASWDs) ASWDs are constructed by first mapping samples to higher-dimensional hypersurfaces parameterized by neural networks. Numerical results demonstrate that the ASWD significantly outperforms other Wasserstein variants for both synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-06-15T23:00:08Z)

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.