Circulant Binary Embedding
This addresses efficiency issues in binary embedding for high-dimensional data, which is incremental as it builds on existing methods with a novel optimization approach.
The paper tackled the problem of high computation and storage costs in binary embedding of high-dimensional data by proposing Circulant Binary Embedding (CBE), which uses circulant matrices and Fast Fourier Transformation to reduce time complexity from O(d^2) to O(d log d) and space complexity from O(d^2) to O(d), while achieving better performance than state-of-the-art methods in experiments.
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.