Fast metric embedding into the Hamming cube

We consider the problem of embedding a subset of $\mathbb{R}^n$ into a low-dimensional Hamming cube in an almost isometric way. We construct a simple and computationally efficient map that achieves this task with high probability: we first apply a specific structured random matrix, which we call the double circulant matrix; using that matrix requires little storage and matrix-vector multiplication can be performed in near-linear time. We then binarize each vector by comparing each of its entries to a random threshold, selected uniformly at random from a well-chosen interval. We estimate the number of bits required for this encoding scheme in terms of two natural geometric complexity parameters of the set -- its Euclidean covering numbers and its localized Gaussian complexity. The estimate we derive turns out to be the best that one can hope for -- up to logarithmic terms. The key to the proof is a phenomenon of independent interest: we show that the double circulant matrix mimics the behavior of a Gaussian matrix in two important ways. First, it yields an almost isometric embedding of any subset of $\ell_2^n$ into $\ell_1^m$ and, second, it maps an arbitrary set in $\mathbb{R}^n$ into a set of well-spread vectors.