Rayan Saab (Theory Seminar)

High dimensional and large data sets often impose a significant burden on applications both in terms of computational complexity and storage cost. 

To reduce these burdens, it is often necessary to obtain lower dimensional, preferably binarized, representations of such data that simultaneously preserve important geometric properties, or even permit accurate reconstruction. Thinking of a set $X \subset \R^N$ as either a high-dimensional data set, or even as a class of signals (such as natural images),  in this talk we present fast methods to replace points from $\mathcal{X}$ with points in a lower-dimensional cube $\{\pm 1\}^m$. That is, we embed $X$ into the binary cube, and we endow the binary cube with a function (a pseudo-metric) that preserves Euclidean distances in the original space. We discuss applications of these ideas to compressed sensing, which deals with efficient data acquisition, as well as on-going work related to machine learning.