Optimal Transport (OT) is the mathematical "gold standard" for comparing probability distributions, but it has a notorious reputation for being slow. While the Sliced Wasserstein (SW) distance has emerged as a lightning-fast alternative, it has long suffered from a major "identity crisis": it can tell you how far apart two datasets are, but it struggles to tell you how to actually map one to the other.
In their paper, Sliced Optimal Transport Plans, Eloi Tanguy, Laetitia Chapel, and Julie Delon bridge this gap. They provide a rigorous theoretical framework for turning these fast distance approximations into actionable "transport plans"—the precise instructions for moving mass from a source to a target in high-dimensional space.
TL;DR
This paper provides a rigorous mathematical foundation for "Pivot Sliced" and "Expected Sliced" transport plans, extending them from simple discrete heuristics to generic probability measures. The authors prove these methods are efficient, theoretically sound, and—in high dimensions—can even recover the exact Wasserstein distance while remaining computationally feasible for millions of points.
What Problem Does This Paper Address?
Optimal Transport is used everywhere from image processing to biology to find the most efficient way to transform one distribution into another. However, computing the exact 2-Wasserstein distance ($W_2$) is computationally heavy, scaling at $O(n^3 \log n)$.
Sliced Wasserstein (SW) solves this by projecting high-dimensional data onto random 1D lines (slices). In 1D, OT is trivial to solve by simply sorting the points. By averaging these 1D distances, we get a very fast distance surrogate.
The catch? Sliced Wasserstein gives you a number (the distance), but it doesn't naturally give you a plan (a high-dimensional coupling or map). If you want to transfer the colors of one image to another or register two 3D shapes, you need the map, not just the distance. Previous attempts to extract these maps were often "heuristics"—they worked in practice for specific cases but lacked the mathematical rigor to guarantee they would work generally.
Methods
The authors introduce and analyze two primary approaches to generate transport plans:
- Pivot Sliced Discrepancy ($PS_\theta$): This method uses a "pivot" measure—specifically the midpoint between two projected distributions—to anchor the transport. By leveraging the theory of $\nu$-based Wasserstein distances, the authors prove that this discrepancy is a semi-metric and relates it to a constrained version of the classic Kantorovich OT problem.
- Expected Sliced Plans: Instead of relying on a single direction, this approach averages "lifted" 1D optimal plans across many random directions. The authors generalize this concept to work with any generic probability measure, not just discrete point clouds.
- Min-Pivot Sliced: They explore an optimization variant where they search for the specific direction $\theta$ that minimizes the discrepancy.
Crucially, the authors provide a Monge formulation for these plans, showing how they can be implemented as simple permutations (sorting) when dealing with discrete point clouds.
Datasets
The theoretical results are validated using several benchmarks:
- Synthetic 2D Distributions: Toy datasets including Gaussians, spirals, "two moons," and circles were used to visualize gradient flows and convergence behavior.
- Color Transfer: Real-world high-resolution images (up to $1280 \times 1024$ pixels) were used to test the ability of the plans to map color distributions between images.
- Shape Registration: The famous Stanford Bunny and Armadillo 3D point clouds (from the
open3dlibrary) were used to evaluate the plans in a rigid registration task.
Key Insights and Ideas
- The "Blessing" of Dimensionality: One of the most striking findings is that in high-dimensional spaces (specifically when the dimension $d \geq 2n-1$), the Min-Pivot Sliced discrepancy actually equals the true 2-Wasserstein distance. This means for high-D data, we can get exact OT results using sliced methods.
- Rigorous Generalization: Most previous work focused only on discrete points. This paper proves that these sliced plans are well-defined for any generic probability measure, providing a much-needed theoretical "safety net" for researchers.
- Sparse vs. Blurred: The authors highlight a trade-off: Pivot Sliced plans tend to be "Monge-like" (point-to-point mappings), whereas Expected Sliced plans are "blurred" (one point maps to many). This makes Pivot Sliced much better for tasks like gradient flows where you need to move points toward a target.
Key Results
- Scalability: While standard OT solvers fail at $n=10^5$ points due to memory constraints, the sliced methods easily handled $n=10^7$ points on a standard laptop.
- Gradient Flow Success: Min-Pivot Sliced successfully converged to target distributions in 2D, whereas the Expected Sliced approach failed to converge—a critical distinction for anyone using OT for generative modeling.
- Shape Registration: In the ICP (Iterative Closest Point) task, Min-Pivot Sliced outperformed standard Wasserstein and other sliced variants in avoiding local minima, leading to more accurate 3D alignments.
Limitations and Future Work
- Triangle Inequality: The $PS_\theta$ discrepancy is a semi-metric, meaning it doesn't always satisfy the triangle inequality. While the authors show it is a metric under specific conditions (atomless projections), this remains a theoretical limitation.
- Non-Linearity: Like all sliced methods, these rely on linear projections. They struggle with highly non-linear data structures (like the "two moons" dataset) unless the data is first augmented or embedded into a higher-dimensional space.
- Directional Sensitivity: The performance of Pivot Sliced is highly dependent on the choice of the direction $\theta$, suggesting that future work could focus on better ways to adaptively choose or optimize these directions.
Summary updated