Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Sparse circulant binary embedding: An asymptotic analysis

Title
Sparse circulant binary embedding: An asymptotic analysis
Authors
Kim, SaehoonCHOI, SEUNGJIN
POSTECH Authors
CHOI, SEUNGJIN
Date Issued
Mar-2018
Publisher
IEEE
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)).
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)).
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
Asymptotic analysis; Binary codes; Bins; Codes (symbols); Hamming distance; Quantization (signal); Vector spaces; Binary embedding; Circulant matrix; Convergence; Locality sensitive hashing; Random projections; sparse embedding; Sparse matrices; Time complexity; Matrix algebra
URI
http://oasis.postech.ac.kr/handle/2014.oak/41165
DOI
10.1109/LSP.2018.2794768
ISSN
1070-9908
Article Type
Article
Citation
IEEE Signal Processing Letters, vol. 25, no. 3, page. 432 - 436, 2018-03
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 CHOI, SEUNGJIN
Dept of Computer Science & Enginrg
Read more

Views & Downloads

Browse