Sparse Circulant Binary Embedding: An Asymptotic Analysis

doi:10.1109/LSP.2018.2794768

Sparse Circulant Binary Embedding: An Asymptotic Analysis

2018-03-01

1

PRE

AI

DOI：10.1109/LSP.2018.2794768

Original

Original request for help

Save

Abstract

En 中文

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)).

Keywords:

Binary embedding (BE)

circulant matrix

locality-sensitive hashing

random projection

sparse embedding

Sparse Circulant Binary Embedding: An Asymptotic Analysis

Abstract

AI Summary

Journal

Organization