Circulant Binary Embedding
Venue
International Conference on Machine Learning (ICML) (2014)
Publication Year
2014
Authors
Felix X. Yu, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang
BibTeX
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 O(d^2) to O(dlogd), and the space complexity from O(d^2)
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.
