Fast Binary Embedding via Circulant Downsampled Matrix -- A
  Data-Independent Approach
  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.
