Can I read Sketching, Embedding, and Dimensionality Reduction for Information Spaces on EtoBox?

Sketching, Embedding, and Dimensionality Reduction for Information Spaces by Abdullah, Amirali; Kumar, Ravi; McGregor, Andrew; Vassilvitskii, Sergei; Venkatasubramanian, Suresh is a scholarly article available to read on EtoBox.

What is Sketching, Embedding, and Dimensionality Reduction for Information Spaces about?

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$ diverg

Author

Abdullah, Amirali; Kumar, Ravi; McGregor, Andrew; Vassilvitskii, Sergei; Venkatasubramanian, Suresh

Published

2015

Language

EN