Fast Binary Embedding via Circulant Downsampled Matrix -- A Data-Independent Approach
This work addresses efficiency issues in binary embedding for applications like image retrieval, but it is incremental as it builds on existing circulant matrix approaches with downsampling.
The paper tackles the problem of high computation and storage costs in binary embedding for high-dimensional data by proposing a fast, data-independent method using downsampling and circulant matrices, achieving O(N + M log M) computation and O(N) storage costs with comparable performance in image applications.
Binary embedding of high-dimensional data aims to produce low-dimensional binary codes while preserving discriminative power. State-of-the-art methods often suffer from high computation and storage costs. We present a simple and fast embedding scheme by first downsampling N-dimensional data into M-dimensional data and then multiplying the data with an MxM circulant matrix. Our method requires O(N +M log M) computation and O(N) storage costs. We prove if data have sparsity, our scheme can achieve similarity-preserving well. Experiments further demonstrate that though our method is cost-effective and fast, it still achieves comparable performance in image applications.