Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

Samet Oymak, Ben Recht

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 Gaus…