Near-optimal Bounds For Binary Embeddings Of Arbitrary Sets

Oymak Samet, Recht Ben. Arxiv 2015

[Paper]    
ARXIV

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.

Similar Work

• A Framework For Similarity Search With Space-time Tradeoffs Using Locality-sensitive Filtering
• Time For Dithering Fast And Quantized Random Embeddings Via The Restricted Isometry Property
• A Quantized Johnson Lindenstrauss Lemma The Finding Of Buffons Needle
• Faster Binary Embeddings For Preserving Euclidean Distances