Scaling Optimal Transport via One-Dimensional Projections

753 concepts425 papers3 proposals

Optimal Transport (OT) provides a mathematically rigorous framework for comparing probability distributions by computing the minimal cost required to transform one distribution into another. While geometrically intuitive and highly effective for capturing structural shifts, exact optimal transport suffers from severe computational bottlenecks. For two empirical distributions of size $n$, computing the standard Wasserstein distance requires solving a linear program with a super-cubic computational complexity of $O(n^3 \log n)$. Furthermore, it suffers from the statistical "curse of dimensionality," meaning the number of samples required to accurately estimate the true distance grows exponentially with the dimension of the space.

Sliced Optimal Transport resolves both bottlenecks simultaneously. By projecting high-dimensional distributions onto one-dimensional lines, the complex multivariate optimization problem decomposes into a collection of independent, computationally trivial sub-problems.

The Efficiency of One-Dimensional Transport

To understand why slicing works, we must first look at optimal transport in a single dimension. When probability distributions are restricted to a one-dimensional line, the optimal transport map is completely determined by monotone rearrangement.

Imagine trying to match two sets of $n$ points on a line such that the sum of the squared distances between matched pairs is minimized. Instead of evaluating all possible permutations, the optimal solution is obtained by simply sorting both datasets in ascending order and matching the $i$-th element of the first set with the $i$-th element of the second.

As highlighted by Soheil Kolouri et al. in Sliced Wasserstein Kernels for Probability Distributions, this sorting mechanism reduces the computational complexity from cubic to $O(n \log n)$. Furthermore, the $L_2$-Wasserstein distance between one-dimensional distributions is isometric to a flat Euclidean space, allowing these distances to be seamlessly integrated into standard Hilbert space frameworks and kernel methods.

The Slicing Mechanism

The core mechanism of Sliced Optimal Transport is to project high-dimensional distributions onto a set of one-dimensional lines (or "slices") using linear projections.

Given a high-dimensional distribution, projecting it onto a unit vector $\theta$ yields a one-dimensional marginal distribution. By choosing a set of directional vectors, we can transform a complex multivariate distribution into a collection of one-dimensional representations that capture the underlying geometric structure along those specific axes.

High-Dimensional Space                  1D Projections (Slices)
     ·   ·                                     |  · · · ·
   ·       ·      --- Project onto θ_1 --->    |---------
     ·   ·                                     |   θ_1

     ·   ·                                     |    ·  ·
   ·       ·      --- Project onto θ_2 --->    |---------
     ·   ·                                     |     θ_2

Once the distributions are projected onto these lines, their one-dimensional Wasserstein distances are computed efficiently via sorting. The global Sliced-Wasserstein (SW) distance is then defined by aggregating these one-dimensional distances. In practice, as detailed in the survey by Abdelwahed Khamis et al. in Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey, this aggregation is typically implemented as an average over a set of random projections sampled uniformly from the unit sphere using Monte Carlo integration.

Escaping the Curse of Dimensionality

Beyond its computational speedup, slicing fundamentally alters the statistical behavior of optimal transport in high dimensions.

Standard Wasserstein distance estimations degrade rapidly as the number of dimensions increases because high-dimensional space is vast and sparsely populated by empirical samples. In contrast, Kimia Nadjahi et al. in Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance proved that Sliced-Wasserstein estimators achieve an asymptotic convergence rate of $\sqrt{n}$, completely bypassing the statistical curse of dimensionality.

This behavior occurs because the actual distance calculations always happen in a one-dimensional space, regardless of how high-dimensional the original data is. As a result, the sample complexity depends on the complexity of the one-dimensional projections rather than the dimensionality of the underlying space. Sloan Nietert et al. in Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances further demonstrated that average-sliced distances exploit the property that projection variance often decreases in higher dimensions, leading to highly stable numerical estimations and superior robustness to outliers.

Finding Informative Projections

While averaging over random projections provides strong global topological guarantees, it can be inefficient if the structural differences between two distributions are concentrated along a few specific directions. Randomly chosen slices might miss these critical axes, treating them as high-dimensional noise.

To address this, the authors of Subspace Robust Wasserstein Distances introduced a optimization framework that identifies a low-dimensional subspace maximizing the Wasserstein distance between the projected distributions. Instead of averaging over all possible directions, this approach actively searches for the directions where the measures are most distinct.

By optimizing the projection vectors to maximize the transport cost, the metric filters out uninformative noise and focuses entirely on the principal geometric differences between the populations. This concept is closely related to Principal Differences Analysis, where Jonas Mueller et al. in Principal Differences Analysis: Interpretable Characterization of Differences between Distributions utilized projection maximization to pinpoint specific features responsible for complex distributional shifts, such as changes in variance or multimodality, which standard mean-focused methods often overlook.

Extensions and Applications

Because sliced optimal transport provides a fast, differentiable, and scalable approximation of distribution alignment, it has been adapted across a wide range of machine learning domains:

  • Gradient Flows and Variational Inference: In Efficient Gradient Flows in Sliced-Wasserstein Space, Clément Bonet et al. demonstrated that replacing the standard Wasserstein distance with its sliced counterpart transforms complex, nested optimization problems into tractable particle updates. This allows gradient flow methods to scale efficiently to high-dimensional tasks like image generation.
  • Unbalanced Mass Transport: Standard optimal transport requires both distributions to have the same total mass. To handle noisy real-world datasets where mass might be created or destroyed, Clément Bonet et al. in Unbalanced Optimal Transport meets Sliced-Wasserstein extended the slicing heuristic to unbalanced transport, solving localized mass relaxation problems within the simplified one-dimensional spaces.
  • Geometric Embeddings: For tasks involving point clouds and multisets, Tal Amir et al. developed the Fourier Sliced-Wasserstein Embedding for Multisets and Measures, which projects data onto random axes and computes the quantile functions of these projections to map complex geometric structures into flat Euclidean spaces while preserving their underlying topology.
  • 3D Point Clouds: In deep learning architectures for 3D data, Trung Nguyen et al. in Point-set Distances for Learning Representations of 3D Point Clouds showed that the sorting-based efficiency of sliced transport allows models to achieve high-fidelity structural alignment in a fraction of the iterations required by traditional, geometrically blind metrics like Chamfer distance.

By reducing the dimensionality of the transport problem before computing the matching cost, Sliced Optimal Transport bridges the gap between the rich geometric properties of optimal mass transport and the computational demands of high-dimensional machine learning applications.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 453 papers
  2. Version 1 · 2026-10-04 · 474 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sliced_optimal_transport_79f452be,
  title = {sliced optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sliced-optimal-transport/rdr_79f452bee7954f26bfe1a1a572e6f953},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_sliced_optimal_transport_79f452be_v2,
  title = {sliced optimal transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sliced-optimal-transport/rdr_79f452bee7954f26bfe1a1a572e6f953/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake