# Binary Embedding: Fundamental Limits and Fast Algorithm

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

## Key facts

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

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

- [Binary Code based Hash Embedding for Web-scale Applications](https://mlsanity.com/paper/2109.02471/) (2021)
- [Highly Efficient 3D Human Pose Tracking from Events with Spiking Spatiotemporal Transformer](https://mlsanity.com/paper/2303.09681/) (2023)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [SpikeVideoFormer: An Efficient Spike-Driven Video Transformer with Hamming Attention and O(T) Complexity](https://mlsanity.com/paper/2505.10352/) (2025)
- [On when is Reservoir Computing with Cellular Automata Beneficial?](https://mlsanity.com/paper/2407.09501/) (2024)

## Abstract (arXiv)

Binary embedding is a nonlinear dimension reduction methodology where high dimensional data are embedded into the Hamming cube while preserving the structure of the original space. Specifically, for an arbitrary N distinct points in mathbbSp-1, our goal is to encode each point using m-dimensional binary strings such that we can reconstruct their geodesic distance up to δ uniform distortion. Existing binary embedding algorithms either lack theoretical guarantees or suffer from running time Obig(mpbig). We make three contributions: (1) we establish a lower bound that shows any binary embedding oblivious to the set of points requires m = Omega(frac1δ2logN) bits and a similar lower bound for non-oblivious embeddings into Hamming distance; (2) [DELETED, see comment]; (3) we also provide an analytic result about embedding a general set of points K subseteq mathbbSp-1 with even infinite size. Our theoretical findings are supported through experiments on both synthetic and real data sets.