  This paper proposes a binarization scheme for vectors of high dimension based
on the recent concept of anti-sparse coding, and shows its excellent
performance for approximate nearest neighbor search. Unlike other binarization
schemes, this framework allows, up to a scaling factor, the explicit
reconstruction from the binary representation of the original vector. The paper
also shows that random projections which are used in Locality Sensitive Hashing
algorithms, are significantly outperformed by regular frames for both synthetic
and real data if the number of bits exceeds the vector dimensionality, i.e.,
when high precision is required.
