# Massively scalable Sinkhorn distances via the Nystr\\"om method Source: [Massively scalable Sinkhorn distances via the Nystr\\"om method]() Collection index: [llms.txt]() Data updated: 2025-10-25T15:28:32.632Z Authors: Jason Altschuler, Francis Bach, Alessandro Rudi, Jonathan Niles-Weed Published: 2018-12-12T23:10:16.000Z ## Abstract The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However, the time and memory requirements of standard algorithms for computing this distance grow quadratically with the size of the data, making them prohibitively expensive on massive data sets. In this work, we show that this challenge is surprisingly easy to circumvent: combining two simple techniques---the Nystr\\"om method and Sinkhorn scaling---provably yields an accurate approximation of the Sinkhorn distance with significantly lower time and memory requirements than other approaches. We prove our results via new, explicit analyses of the Nystr\\"om method and of the stability properties of Sinkhorn scaling. We validate our claims experimentally by showing that our approach easily computes Sinkhorn distances on data sets hundreds of times larger than can be handled by other techniques. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [ED time point prediction on Echocardiogram videos 100 randomly selected (test)](): ED time point prediction; Echocardiogram videos 100 randomly selected (test); Error: 0.31. - [ED Time Point Prediction on Echocardiogram 100 videos](): ED time point prediction; Echocardiogram 100 videos; Prediction Error: 45. ## Original sources and implementation [Original paper]() [PDF]()