Abstract
Optimal Transport (OT) and Wasserstein distances are essential for comparing probability distributions but suffer from high computational costs and memory requirements, especially in high-dimensional settings. This paper introduces Stream-SW, the first method to estimate Sliced Wasserstein (SW) distances from continuous data streams without storing all samples. By leveraging the 1D projection property of SW and efficient quantile sketches (KKL), Stream-SW achieves near-linear time complexity and logarithmic space complexity. Theoretical guarantees and empirical evaluations on point clouds and gesture datasets demonstrate its effectiveness for real-time applications.
Introduction
Comparing probability distributions is a fundamental task in machine learning, with applications ranging from generative modeling to point cloud analysis. The Wasserstein distance is a popular metric for this purpose, yet it is computationally expensive ($O(n^3 \log n)$) and suffers from the curse of dimensionality. Sliced Wasserstein (SW) addresses the dimensionality issue by projecting data onto random 1D lines, where the distance has a closed-form solution. However, standard SW still requires storing all $n$ data points, creating a "memory wall" for streaming data applications like IoT or real-time sensor monitoring.
Stream-SW overcomes these limitations by combining Sliced Optimal Transport with streaming quantile approximation. This allows for distance estimation on the fly with a memory footprint that grows only logarithmically with the number of samples.
Methodology
The Stream-SW algorithm bridges the gap between high-dimensional optimal transport and 1D quantile estimation.
The Slicing Property
The core idea of SW is to decompose a high-dimensional OT problem into several 1D problems. In one dimension, the Wasserstein distance between two distributions is simply the $L_p$ distance between their quantile functions. This transformation is crucial because it turns a complex optimization problem into a quantile matching problem.
Streaming Quantile Sketches
To avoid storing all data points, Stream-SW utilizes the Karnin-Lang-Liberty (KKL) sketch. The KKL sketch is a hierarchical data structure that maintains a small, weighted subset of samples to estimate any quantile with high accuracy using only $O(\log n)$ space.
The Stream-SW Algorithm
As data points arrive in a stream, the algorithm performs the following steps:
- Projection: Each new point is projected onto $L$ pre-defined random directions.
- Sketch Update: The $L$ corresponding quantile sketches are updated with the new 1D projections.
- Compacting: Periodically, the sketches undergo a "compacting" operation to maintain the logarithmic space bound while preserving accuracy.
- Distance Computation: To estimate the SW distance, the algorithm queries the sketches to reconstruct the 1D Wasserstein distance for each projection and averages them.
Key Insights
- Quantile-Centric Approach: By recognizing that 1D OT is a quantile matching problem, the authors leverage decades of research in database streaming algorithms for optimal transport.
- Logarithmic Space Complexity: The memory requirement grows as $O(\log n)$, enabling the processing of massive datasets on devices with limited memory.
- Mergeability: KKL sketches are mergeable, making Stream-SW naturally compatible with distributed systems.
Experimental Results
The authors evaluated Stream-SW on synthetic mixtures, 3D point clouds (ModelNet10, ShapeNet), and real-world gesture data (MSRC-12).
- Accuracy vs. Memory: Stream-SW significantly outperforms naive random subsampling. For the same memory budget, it provides a much tighter approximation of the true SW distance.
- Point Cloud Classification: On ModelNet10, Stream-SW achieved classification accuracies (up to ~77%) comparable to "Full SW" using all data, even with very small sketch sizes.
- Real-time Change Detection: In the MSRC-12 gesture dataset, Stream-SW successfully detected transitions between actions (e.g., from bending to throwing) with minimal delay, outperforming traditional sliding-window methods.
Conclusion and Future Work
Stream-SW provides a scalable and memory-efficient solution for computing Sliced Wasserstein distances in streaming environments. While the current work assumes compact support for theoretical bounds and uses fixed projections, future extensions could explore "Streaming Max-Sliced Wasserstein" with adaptive projections or applications to non-Euclidean manifolds.
Summary updated