Circulant Binary Embedding

By Felix X. Yu, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang. 2014

185 citations recorded by the source corpus.

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(d log d), 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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Recent advances in convolutional neural networks (2015, background): “x. The space complexity of Adaptive Fastfood transform is O (n ), and the time complexity is O (n log n ). Motivated by the great advantages of circulant matrix in both space and computation eciency [166, 167], Cheng et al . [168] explore the redundancy in the parametrization of fully-connected laye”
Orthogonal Random Features (2016, methodology): “Structured matrices have been used for speeding up dimensionality reduction [1], binary embedding [27], deep neural networks [5] and kernel approximation [13, 28, 7].”
Sparse composite quantization (2015, methodology): “The approximate nearest neighbor search algorithms are in general developed from two main aspects: (1) comparing the query with only a small subset of database vectors through special data structures, such as k-d trees [4, 31], FLANN [19], and neighborhood graph [26, 30], and (2) accelerating the di”
Hashing for Similarity Search: A Survey (2014, methodology): “an recent work, circulant binary embedding [143], formulates the projection matrix (the weights in the hash function) using a circular matrix R = circ(r).”
Sparse projections for high-dimensional binary codes (2015, methodology): “LSH has been shown [ 11, 10, 32] to have competitive performance when b ∼ O ( d ) .”
A Survey on Learning to Hash (2016, background): “A recent work, circulant binary embedding [165], accelerates the encoding process for the linear hash functions, and”
Deep Hashing Network for Efficient Similarity Retrieval (2016, background): “…(Kulis and Darrell 2009; Gong and Lazebnik 2011; Norouzi and Blei 2011; Fleet, Punjani, and Norouzi 2012; Liu et al. 2012; Wang, Kumar, and Chang 2012; Liu et al. 2013; Gong et al. 2013; Yu et al. 2014; Xia et al. 2014; Zhang et al. 2014; Shen et al. 2015; Lai et al. 2015; Erin Liong et al. 2015).”
Deep Cauchy Hashing for Hamming Space Retrieval (2018, methodology): “Existing hashing methods [2, 16, 12, 26, 22, 30, 25, 11, 34, 35, 24] consist of unsupervised and supervised hashing.”
An Exploration of Parameter Redundancy in Deep Networks with Circulant Projections (2015, methodology): “The idea of replacing the unstructured projection with the circulant projection is motivated by using circulant projections in dimensionality reduction [41], binary embedding [43], and kernel approximation [44].”
HashNet: Deep Learning to Hash by Continuation (2017, methodology): “Many learning to hash methods have been proposed to enable efficient ANN search of high-dimensional data by ranking the Hamming distance across compact binary hash codes [19, 12, 27, 9, 23, 34, 25, 11, 38, 39].”
Deep Cross-Modal Hashing (2016, background): “Due to its low storage cost and fast retrieval speed, hashing has recently attracted much attention from the ANN research community (Weiss et al., 2008; Raginsky & Lazebnik, 2009; Wang et al., 2010; Liu et al., 2011; Norouzi & Fleet, 2011; Norouzi et al., 2012; Rastegari et al., 2013; Yu et al., 201”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “Another effective hash code ranking method is the query-sensitive hashing, which explores the raw feature of the query sample and learns query-specific weights of hash bits to achieve accurate ǫnearest neighbor search [94].”
Progressive Generative Hashing for Image Retrieval (2018, methodology): “…learnt the projection based hash functions by leveraging the information contained in the data [Weiss et al. , 2008; Gong and Lazebnik, 2011; Wang et al. , 2017; Liu et al. , 2014b; Wang et al. , 2018; Kong and Li, 2012; Yu et al. , 2014; Liu et al. , 2014a; Shen et al. , 2015; Wang et al. , 2014].”
LLMs Meet Isolation Kernel: Lightweight, Learning-free Binary Embeddings for Fast Retrieval (2026, unknown): “Hashing techniques can be broadly categorized into training-based approaches (Learning to Hash, L2H) (Liu et al., 2024a; Weiss et al., 2008; Yu et al., 2014; Gong et al., 2013b,a; Xia et al., 2015; Jin et al., 2013; Zhu et al., 2014; Lan et al., 2017) and learning-free approaches (Charikar, 2002;…”