# Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

arXiv: https://arxiv.org/abs/1512.04433 · HTML: https://mlsanity.com/paper/1512.04433/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2015.

## Built on by (most cited first, 5 of 5)

- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable](https://mlsanity.com/paper/2205.11716/) (2022)
- [Learning to Reconstruct Signals From Binary Measurements](https://mlsanity.com/paper/2303.08691/) (2023)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Hyperdimensional Cross-Modal Alignment of Frozen Language and Image Models for Efficient Image Captioning](https://mlsanity.com/paper/2602.23588/) (2026)

## Abstract (arXiv)

We study embedding a subset K of the unit sphere to the Hamming cube -1,+1m. We characterize the tradeoff between distortion and sample complexity m in terms of the Gaussian width ω(K) of the set. For subspaces and several structured sets we show that Gaussian maps provide the optimal tradeoff m~ δ-2ω2(K), in particular for δ distortion one needs m≈δ-2d where d is the subspace dimension. For general sets, we provide sharp characterizations which reduces to m≈δ-4ω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.