Circulant Binary Embedding

Abstract

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 $\mathcal{O}(d^2)$ to $\mathcal{O}(d\log d)$, and the space complexity from $\mathcal{O}(d^2)$ to $\mathcal{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.

ICML 2014

References in corpus (2)

• Hashing Algorithms for Large-Scale Learning
• New bounds for circulant Johnson-Lindenstrauss embeddings

Cited by in corpus (19)

• Compact Nonlinear Maps and Circulant Extensions
• Deep Cross-Modal Hashing
• Learning to Hash for Indexing Big Data - A Survey
• Binary Embedding: Fundamental Limits and Fast Algorithm
• Binary embeddings with structured hashed projections
• Making Online Sketching Hashing Even Faster
• On Binary Embedding using Circulant Matrices
• On the Evaluation Metric for Hashing
• A Proposal-based Approach for Activity Image-to-Video Retrieval
• Friction from Reflectance: Deep Reflectance Codes for Predicting Physical Surface Properties from One-Shot In-Field Reflectance
• Parameter Efficient Deep Neural Networks with Bilinear Projections
• Deep Multi-Index Hashing for Person Re-Identification
• Optimal Projection Guided Transfer Hashing for Image Retrieval
• Widening and Squeezing: Towards Accurate and Efficient QNNs
• Building Compact and Robust Deep Neural Networks with Toeplitz Matrices
• Faster Binary Embeddings for Preserving Euclidean Distances
• Implicit Sparse Code Hashing
• Query-Adaptive Hash Code Ranking for Large-Scale Multi-View Visual Search
• Composite Quantization