Tree-Sliced Wasserstein Distance on a System of Lines
- URL: http://arxiv.org/abs/2406.13725v1
- Date: Wed, 19 Jun 2024 17:40:11 GMT
- Title: Tree-Sliced Wasserstein Distance on a System of Lines
- Authors: Viet-Hoang Tran, Trang Pham, Tho Tran, Tam Le, Tan M. Nguyen,
- Abstract summary: 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.
- Score: 7.382959387042827
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sliced Wasserstein (SW) distance in Optimal Transport (OT) is widely used in various applications thanks to its statistical effectiveness and computational efficiency. On the other hand, Tree Wassenstein (TW) and Tree-sliced Wassenstein (TSW) are instances of OT for probability measures where its ground cost is a tree metric. TSW also has a low computational complexity, i.e. linear to the number of edges in the tree. Especially, TSW is identical to SW when the tree is a chain. While SW is prone to loss of topological information of input measures due to relying on one-dimensional projection, TSW is more flexible and has a higher degree of freedom by choosing a tree rather than a line to alleviate the curse of dimensionality in SW. However, for practical applications, popular tree metric sampling methods are heavily built upon given supports, which limits their capacity to adapt to new supports. In this paper, we propose the Tree-Sliced Wasserstein distance on a System of Lines (TSW-SL), which brings a connection between SW and TSW. Compared to SW and TSW, our TSW-SL benefits from the higher degree of freedom of TSW while being suitable to dynamic settings as SW. 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. We empirically verify the advantages of TSW-SL over the traditional SW by conducting a variety of experiments on gradient flows, image style transfer, and generative models.
Related papers
- Generalized Linear Mode Connectivity for Transformers [87.32299363530996]
A striking phenomenon is linear mode connectivity (LMC), where independently trained models can be connected by low- or zero-loss paths.<n>Prior work has predominantly focused on neuron re-ordering through permutations, but such approaches are limited in scope.<n>We introduce a unified framework that captures four symmetry classes: permutations, semi-permutations, transformations, and general invertible maps.<n>This generalization enables, for the first time, the discovery of low- and zero-barrier linear paths between independently trained Vision Transformers and GPT-2 models.
arXiv Detail & Related papers (2025-06-28T01:46:36Z) - Tree-Sliced Wasserstein Distance with Nonlinear Projection [8.996793030061324]
Tree-Sliced methods have emerged as an alternative to the traditional Sliced Wasserstein (SW) distance.<n>We propose a novel nonlinear projectional framework for the Tree-Sliced Wasserstein (TSW) distance, replacing the linear projections in earlier versions with general projections.<n>We validate our proposed metric through extensive numerical experiments for Euclidean and spherical datasets.
arXiv Detail & Related papers (2025-05-02T03:06:25Z) - Spherical Tree-Sliced Wasserstein Distance [6.967581304933985]
We present an adaptation of tree systems on OT problems for measures supported on a sphere.
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) - Distance-Based Tree-Sliced Wasserstein Distance [6.967581304933985]
We propose a novel class of splitting maps that generalizes the existing one studied in Tree-Sliced Wasserstein distance on Systems of Lines.
We show that Db-TSW significantly improves accuracy compared to recent SW variants while maintaining low computational cost.
arXiv Detail & Related papers (2025-03-14T03:36:44Z) - Erwin: A Tree-based Hierarchical Transformer for Large-scale Physical Systems [48.984420422430404]
We present Erwin, a hierarchical transformer inspired by methods from computational many-body physics.<n>We demonstrate Erwin's effectiveness across multiple domains, including cosmology, molecular dynamics, PDE solving, and particle fluid dynamics.
arXiv Detail & Related papers (2025-02-24T10:16:55Z) - Towards Better Spherical Sliced-Wasserstein Distance Learning with Data-Adaptive Discriminative Projection Direction [41.056943683319176]
In the original Spherical Sliced-Wasserstein, all projection directions are treated equally.
We propose a novel data-adaptive Discriminative Spherical Sliced-Wasserstein (DSSW) distance.
arXiv Detail & Related papers (2024-12-26T13:23:37Z) - Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy [12.2853783834605]
We propose a new tree-Wasserstein distance (TWD) for high-dimensional data with two key aspects.
First, our TWD is specifically designed for data with a latent feature hierarchy, i.e., the features lie in a hierarchical space.
We show that our TWD computed based on data observations provably recovers the TWD defined with the latent feature hierarchy.
arXiv Detail & Related papers (2024-10-28T15:11:23Z) - 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) - A Geometrical Approach to Evaluate the Adversarial Robustness of Deep
Neural Networks [52.09243852066406]
Adversarial Converging Time Score (ACTS) measures the converging time as an adversarial robustness metric.
We validate the effectiveness and generalization of the proposed ACTS metric against different adversarial attacks on the large-scale ImageNet dataset.
arXiv Detail & Related papers (2023-10-10T09:39:38Z) - Fast Optimal Transport through Sliced Wasserstein Generalized Geodesics [14.259614797710224]
min-SWGG is a proxy of the squared WD based on an optimal one-dimensional projection of the two input distributions.
We show that min-SWGG is an upper bound of WD and that it has a complexity similar to Sliced-Wasserstein.
Empirical evidences support the benefits of min-SWGG in various contexts.
arXiv Detail & Related papers (2023-07-04T15:20:41Z) - Automated classification of pre-defined movement patterns: A comparison
between GNSS and UWB technology [55.41644538483948]
Real-time location systems (RTLS) allow for collecting data from human movement patterns.
The current study aims to design and evaluate an automated framework to classify human movement patterns in small areas.
arXiv Detail & Related papers (2023-03-10T14:46:42Z) - 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) - 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) - LAB-Net: LAB Color-Space Oriented Lightweight Network for Shadow Removal [82.15476792337529]
We present a novel lightweight deep neural network that processes shadow images in the LAB color space.
The proposed network termed "LAB-Net", is motivated by the following three observations.
Experimental results show that our LAB-Net well outperforms state-of-the-art methods.
arXiv Detail & Related papers (2022-08-27T15:34:15Z) - Auto-Weighted Layer Representation Based View Synthesis Distortion
Estimation for 3-D Video Coding [78.53837757673597]
In this paper, an auto-weighted layer representation based view synthesis distortion estimation model is developed.
The proposed method outperforms the relevant state-of-the-art methods in both accuracy and efficiency.
arXiv Detail & Related papers (2022-01-07T12:12:41Z) - A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework.
We develop a geometric theory that improves and generalises this construction to any manifold.
arXiv Detail & Related papers (2021-05-06T17:36:55Z) - ResNet-LDDMM: Advancing the LDDMM Framework Using Deep Residual Networks [86.37110868126548]
In this work, we make use of deep residual neural networks to solve the non-stationary ODE (flow equation) based on a Euler's discretization scheme.
We illustrate these ideas on diverse registration problems of 3D shapes under complex topology-preserving transformations.
arXiv Detail & Related papers (2021-02-16T04:07:13Z) - Learning to Beamform in Heterogeneous Massive MIMO Networks [48.62625893368218]
It is well-known problem of finding the optimal beamformers in massive multiple-input multiple-output (MIMO) networks.
We propose a novel deep learning based paper algorithm to address this problem.
arXiv Detail & Related papers (2020-11-08T12:48:06Z) - Convex Polytope Trees [57.56078843831244]
convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary.
We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
arXiv Detail & Related papers (2020-10-21T19:38:57Z) - A Flexible Pipeline for the Optimization of CSG Trees [3.622365857213782]
CSG trees are an intuitive, yet powerful technique for the representation of geometry using a combination of Boolean set-operations and geometric primitives.
We present a systematic comparison of newly developed and existing tree optimization methods and propose a flexible processing pipeline with a focus on tree editability.
arXiv Detail & Related papers (2020-08-09T06:45:10Z) - Distributional Sliced-Wasserstein and Applications to Generative
Modeling [27.014748003733544]
Sliced-Wasserstein distance (SW) and its variant, Max Sliced-Wasserstein distance (Max-SW) have been used widely in the recent years.
We propose a novel distance, named Distributional Sliced-Wasserstein distance (DSW)
We show that the DSW is a generalization of Max-SW, and it can be computed efficiently by searching for the optimal push-forward measure.
arXiv Detail & Related papers (2020-02-18T04:35:16Z) - Understanding Graph Neural Networks with Generalized Geometric
Scattering Transforms [67.88675386638043]
The scattering transform is a multilayered wavelet-based deep learning architecture that acts as a model of convolutional neural networks.
We introduce windowed and non-windowed geometric scattering transforms for graphs based upon a very general class of asymmetric wavelets.
We show that these asymmetric graph scattering transforms have many of the same theoretical guarantees as their symmetric counterparts.
arXiv Detail & Related papers (2019-11-14T17:23:06Z)
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.