  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.
