On the Optimal Bit Complexity of Circulant Binary Embedding

Saehoon Kim, Jungtaek Kim, Seungjin Choi

Abstract

Circulant Binary Embedding (CBE) offers significant computational advantages over unstructured random projections for high-dimensional data mapping. However, proving its theoretical optimality has been challenging due to the statistical dependencies introduced by the circulant structure. This paper bridges this gap, demonstrating that CBE achieves the optimal bit complexity of $O(\epsilon^{-2} \log n)$, matching the accuracy of slower unstructured methods while maintaining nearly linear time and space complexities.

Introduction

Binary Embedding (BE) is a critical technique for large-scale similarity search, mapping high-dimensional vectors into compact binary strings to preserve distances. While unstructured random projections are the "gold standard" for accuracy, requiring $k = O(\epsilon^{-2} \log n)$ bits, they suffer from $O(d^2)$ time and space complexity. Circulant Binary Embedding (CBE) addresses this by using circulant matrices, enabling Fast Fourier Transform (FFT) based computations with $O(d \log d)$ time and $O(d)$ space. Despite its practical success, the statistical dependency between bits in CBE has historically hindered proofs of its optimal performance.

Methodology

The authors establish a new theoretical framework to prove CBE's optimality. Key components include:

  • Rademacher Sequences: Utilizing independent $\pm 1$ values instead of Gaussian sequences, aligning with practical implementations and improving empirical performance.
  • Orthogonal Decomposition: To address bit dependency, the authors decompose circulant pairs, analyzing how these dependencies diminish as the data dimension $d$ grows.
  • Incoherence Assumptions: The proof assumes the dataset has a small $l_\infty$ norm (low coherence). For "spiky" datasets, a randomized Hadamard transform is typically used as a pre-processing step to satisfy this condition.
Convergence of error terms $\|\widehat{p}_{i,m}\|_2$ and $|g^\top \widehat{p}_{i,m}|$ as dimension increases for different angles.

Key Insights

The central finding is that the statistical dependency inherent in CBE becomes negligible in high-dimensional spaces. As the data dimension $d$ increases, the behavior of CBE converges to that of independent projections.

Performance comparison of Circulant vs. Independent embedding across dimensions $d=5, 10, 20, 30$. The gap narrows as $d$ increases.

Furthermore, the paper demonstrates that a single circulant layer is sufficient for optimal complexity, refuting previous suggestions that multi-layer embeddings were necessary. The use of Rademacher sign-flipping is also shown to preserve angles more effectively than Gaussian noise in the circulant context.

Results

The theoretical analysis confirms that CBE guarantees $\epsilon$-distortion with $k = O(\epsilon^{-2} \log n)$ bits, the first such proof for this method. Empirically, evaluations on MNIST, CIFAR-10, and GIST1M benchmarks show that CBE's performance in angle preservation and nearest neighbor search is virtually identical to unstructured BE, while maintaining its massive lead in computational efficiency.

Conclusion

This work provides the long-sought theoretical justification for the efficiency of Circulant Binary Embedding. By proving its optimal bit complexity, the authors solidify CBE as a robust and scalable solution for high-dimensional data processing in large-scale applications. Future work may explore extending these bounds to non-angular distance metrics or more complex structured matrices.

Summary updated

Abstract

Binary embedding refers to methods for embedding points in R d into vertices of a Hamming cube of dimension k, such that the normalized Hamming distance well preserves the pre-defined similarity between vectors in the original space. A common approach to binary embedding is to use random projection with unstructured projection, followed by one-bit quantization to produce binary codes, which has been proven that k
BibTeX
@inproceedings{kim2018optimal,
  author = {Saehoon Kim and Jungtaek Kim and Seungjin Choi},
  title = {{On the Optimal Bit Complexity of Circulant Binary Embedding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11818},
}
Figure