Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
  We study embedding a subset $K$ of the unit sphere to the Hamming cube
$\{-1,+1\}^m$. We characterize the tradeoff between distortion and sample
complexity $m$ in terms of the Gaussian width $\omega(K)$ of the set. For
subspaces and several structured sets we show that Gaussian maps provide the
optimal tradeoff $m\sim \delta^{-2}\omega^2(K)$, in particular for $\delta$
distortion one needs $m\approx\delta^{-2}{d}$ where $d$ is the subspace
dimension. For general sets, we provide sharp characterizations which reduces
to $m\approx{\delta^{-4}}{\omega^2(K)}$ after simplification. We provide
improved results for local embedding of points that are in close proximity of
each other which is related to locality sensitive hashing. We also discuss
faster binary embedding where one takes advantage of an initial sketching
procedure based on Fast Johnson-Lindenstauss Transform. Finally, we list
several numerical observations and discuss open problems.
