  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.
