Fast Binary Embeddings with Gaussian Circulant Matrices: Improved Bounds

Sjoerd Dirksen, Alexander Stollenwerk

Research output: Contribution to journalArticleAcademicpeer-review


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
Issue number3
Publication statusPublished - 13 Feb 2018
Externally publishedYes


  • Binary embeddings
  • Johnson–Lindenstrauss embeddings
  • Circulant matrices


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

Cite this