Sketching information divergences

摘要

When comparing discrete probability distributions, natural measures of similarity are not ℓ p distances but rather are information divergences such as Kullback-Leibler and Hellinger. This paper considers some of the issues related to constructing small-space sketches of distributions in the data-stream model, a concept related to dimensionality reduction, such that these measures can be approximated from the sketches. Related problems for ℓ p distances are reasonably well understood via a series of results by Johnson and Lindenstrauss (Contemp. Math. 26:189–206, 1984), Alon et al. (J. Comput. Syst. Sci. 58(1):137–147, 1999), Indyk (IEEE Symposium on Foundations of Computer Science, pp. 202–208, 2000), and Brinkman and Charikar (IEEE Symposium on Foundations of Computer Science, pp. 514–523, 2003). In contrast, almost no analogous results are known to date about constructing sketches for the information divergences used in statistics and learning theory.