Fast Binary Embeddings with Gaussian Circulant Matrices: Improved Bounds

Sjoerd Dirksen, Alexander Stollenwerk

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We consider the problem of encoding a finite set of vectors into a small number of bits while approximately retaining information on the angular distances between the vectors. By deriving improved variance bounds related to binary Gaussian circulant embeddings, we largely fix a gap in the proof of the best known fast binary embedding method. Our bounds also show that well-spreadness assumptions on the data vectors, which were needed in earlier work on variance bounds, are unnecessary. In addition, we propose a new binary embedding with a faster running time on sparse data.
Original languageEnglish
Pages (from-to)599-626
Number of pages28
JournalDiscrete and Computational Geometry
Volume60
Issue number3
DOIs
Publication statusPublished - 13 Feb 2018
Externally publishedYes

Keywords

  • Binary embeddings
  • Johnson–Lindenstrauss embeddings
  • Circulant matrices

Fingerprint

Dive into the research topics of 'Fast Binary Embeddings with Gaussian Circulant Matrices: Improved Bounds'. Together they form a unique fingerprint.

Cite this