# Circulant Binary Embedding

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2014.

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

- [Unsupervised Hashing with Semantic Concept Mining](https://mlsanity.com/paper/2209.11475/) (2022)
- [Parameter-Efficient Fine-Tuning via Circular Convolution](https://mlsanity.com/paper/2407.19342/) (2024)
- [Composing Linear Layers from Irreducibles](https://mlsanity.com/paper/2507.11688/) (2025)
- [Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing](https://mlsanity.com/paper/2306.02563/) (2023)
- [Improving LSH via Tensorized Random Projection](https://mlsanity.com/paper/2402.07189/) (2024)
- [Compositional Kronecker Context Optimization for Vision-Language Models](https://mlsanity.com/paper/2403.11631/) (2024)

## Abstract (arXiv)

Binary embedding of high-dimensional data requires long codes to preserve the discriminative power of the input space. Traditional binary coding methods often suffer from very high computation and storage costs in such a scenario. To address this problem, we propose Circulant Binary Embedding (CBE) which generates binary codes by projecting the data with a circulant matrix. The circulant structure enables the use of Fast Fourier Transformation to speed up the computation. Compared to methods that use unstructured matrices, the proposed method improves the time complexity from O(d2) to O(dlogd), and the space complexity from O(d2) to O(d) where d is the input dimensionality. We also propose a novel time-frequency alternating optimization to learn data-dependent circulant projections, which alternatively minimizes the objective in original and Fourier domains. We show by extensive experiments that the proposed approach gives much better performance than the state-of-the-art approaches for fixed time, and provides much faster computation with no performance degradation for fixed number of bits.