  Binary embedding is the problem of mapping points from a high-dimensional
space to a Hamming cube in lower dimension while preserving pairwise distances.
An efficient way to accomplish this is to make use of fast embedding techniques
involving Fourier transform e.g.~circulant matrices. While binary embedding has
been studied extensively, theoretical results on fast binary embedding are
rather limited. In this work, we build upon the recent literature to obtain
significantly better dependencies on the problem parameters. A set of $N$
points in $\mathbb{R}^n$ can be properly embedded into the Hamming cube $\{\pm
1\}^k$ with $\delta$ distortion, by using $k\sim\delta^{-3}\log N$ samples
which is optimal in the number of points $N$ and compares well with the optimal
distortion dependency $\delta^{-2}$. Our optimal embedding result applies in
the regime $\log N\lesssim n^{1/3}$. Furthermore, if the looser condition $\log
N\lesssim \sqrt{n}$ holds, we show that all but an arbitrarily small fraction
of the points can be optimally embedded. We believe our techniques can be
useful to obtain improved guarantees for other nonlinear embedding problems.
