Article

Cited *0* time in
Cited *0* time in

Metadata Downloads

Sparse circulant binary embedding: An asymptotic analysis

- Title
- Sparse circulant binary embedding: An asymptotic analysis

- Authors
- Kim, Saehoon; CHOI, 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

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

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

- CHOI, SEUNGJIN
- Dept of Computer Science & Enginrg

OAK

library@postech.ac.kr
*Tel: 054-279-2548*

Copyrights © by 2017 Pohang University of Science and Technology All right reserved.