Sparse circulant binary embedding: An asymptotic analysis

Abstract

Binary embedding refers to methods for embedding points in R-d into vertices in the Hamming cube of dimension O(d), such that the normalized Hamming distance between the codes preserves a prespecified distance between vectors in the original space. A common approach to binary embedding is to use random projection, followed by one-bit quantization to produce binary codes. Of particular interest, in this letter, is sparse circulant binary embedding (SCBE), where a sparse random circulant matrix with random sampling at a rate of 1 - s for s. (0, 1) is used for random projection. The SCBE has the space complexity O((1 - s) d), while unstructured random projection has the space complexity O(d(2)). We present an asymptotic analysis of SCBE, when d approaches infinity, showing that the performance of SCBE is comparable to that of binary embedding with unstructured random projection while the former has the space complexity O((1 - s) d) and the time complexity O(d log d) but the latter has both space and time complexities O(d(2)).