# Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2016.

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

- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [Integrating Intermediate Layer Optimization and Projected Gradient Descent for Solving Inverse Problems with Diffusion Models](https://mlsanity.com/paper/2505.20789/) (2025)
- [Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance](https://mlsanity.com/paper/2405.11095/) (2024)

## Abstract (arXiv)

Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g.~circulant matrices. While binary embedding has been studied extensively, theoretical results on fast binary embedding are rather limited. In this work, we build upon the recent literature to obtain significantly better dependencies on the problem parameters. A set of N points in ℝn can be properly embedded into the Hamming cube ± 1k with δ distortion, by using k~δ-3log N samples which is optimal in the number of points N and compares well with the optimal distortion dependency δ-2. Our optimal embedding result applies in the regime log Nlesssim n1/3. Furthermore, if the looser condition log Nlesssim √n holds, we show that all but an arbitrarily small fraction of the points can be optimally embedded. We believe our techniques can be useful to obtain improved guarantees for other nonlinear embedding problems.