Streaming Sliced Optimal Transport

Sliced optimal transport (SOT), or sliced Wasserstein (SW) distance, is widely recognized for its statistical and computational scalability. In this work, we further enhance computational scalability by proposing the first method for estimating SW from sample streams, called streaming sliced Wasserstein (Stream-SW). To define Stream-SW, we first introduce a streaming estimator of the one-dimensional Wasserstein distance (1DW). Since the 1DW has a closed-form expression, given by the integral of the absolute difference between the quantile functions of the compared distributions, we leverage quantile approximation techniques for sample streams to define a streaming 1DW estimator. By applying the streaming 1DW to all projections, we obtain Stream-SW. The key advantage of Stream-SW is its low memory complexity while providing theoretical guarantees on the approximation error. We demonstrate that Stream-SW achieves a more accurate approximation of SW than random subsampling, with lower memory consumption, when comparing Gaussian distributions and mixtures of Gaussians from streaming samples. Additionally, we conduct experiments on point cloud classification, point cloud gradient flows, and streaming change point detection to further highlight the favorable performance of the proposed Stream-SW.

Comparing two collections of data points, like detecting changes in sensor readings or classifying 3D shapes, requires measuring how different their underlying distributions are. The standard tool for this, called the Wasserstein distance, becomes impractical when data arrives as a continuous stream, since storing everything is impossible on memory-limited devices like IoT sensors. We developed Stream-SW, the first streaming algorithm for the Sliced Wasserstein distance, by combining compact "quantile sketch" data structures with sliced optimal transport. Our method processes each incoming data point on the fly, using memory that grows only logarithmically with the number of samples seen, making it feasible on constrained hardware. We proved rigorous guarantees on how accurately Stream-SW approximates the true distance, and showed it outperforms the naive alternative of keeping only a random subset of the data. Experiments on point-cloud classification, gradient flows, and gesture-based change-point detection confirm that Stream-SW delivers better accuracy and downstream performance in realistic streaming scenarios, opening the door to reliable distribution comparison on edge devices.