I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika
Inside specifically had this statement.
Picking a random hyperplane amounts to choosing a normally
distributed random variable for each dimension. Thus
even representing a hash function in this family could require
a large number of random bits. However, for n vectors, the
hash functions can be chosen by picking O(log^2 n) random
bits, i.e. we can restrict the random hyperplanes to be in
a family of size 2^O(log^2 n)
I think it didnt make sense as what it means is that for each n vector, the dimensions would be log^2 n. However, the equivalent statement is that the hyperplanes can be in a family of size 2^O(log^2 n)
It doesnt seem to make any sense to me. Can someone explain to me why is this statement equals.
Thanks.
If you are picking $O(\log^2 n)$ bits, then the number of values that can be represented by those bits is $2^{O(\log^2 n))}$.
That is, $m$ bits can represent $2^m$ values.