  Information distances like the Hellinger distance and the Jensen-Shannon
divergence have deep roots in information theory and machine learning. They are
used extensively in data analysis especially when the objects being compared
are high dimensional empirical probability distributions built from data.
However, we lack common tools needed to actually use information distances in
applications efficiently and at scale with any kind of provable guarantees. We
can't sketch these distances easily, or embed them in better behaved spaces, or
even reduce the dimensionality of the space while maintaining the probability
structure of the data.
  In this paper, we build these tools for information distances---both for the
Hellinger distance and Jensen--Shannon divergence, as well as related measures,
like the $\chi^2$ divergence. We first show that they can be sketched
efficiently (i.e. up to multiplicative error in sublinear space) in the
aggregate streaming model. This result is exponentially stronger than known
upper bounds for sketching these distances in the strict turnstile streaming
model. Second, we show a finite dimensionality embedding result for the
Jensen-Shannon and $\chi^2$ divergences that preserves pair wise distances.
Finally we prove a dimensionality reduction result for the Hellinger,
Jensen--Shannon, and $\chi^2$ divergences that preserves the information
geometry of the distributions (specifically, by retaining the simplex structure
of the space). While our second result above already implies that these
divergences can be explicitly embedded in Euclidean space, retaining the
simplex structure is important because it allows us to continue doing inference
in the reduced space. In essence, we preserve not just the distance structure
but the underlying geometry of the space.
