non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to which side of the hyperplane a data point lies. I want to use locality sensitive hashing with a random projection, but I need to be able to produce more than just two possible indexes.

I'm wondering if I could make an LSH by binning data according to this strategy:

1. Initialize a d x k matrix, where d is the input data dimensionality and k is the number of hash indexes we want.
2. Project incoming data into k-dimensional space using this matrix.
3. Take the argmax of the new k-dimensional vector. In other words, output the dimension that has the largest value.

If not, does anyone know of another technique? Thanks!

• I mean that dimension-wise - the dimension that has the largest value. Jan 2 '18 at 16:23

Let $h_r(x)$ be a hash function that hashes a point $x$ to a one-bit hash output. Then you can construct a hash function that gives you a $b$-bit hash output, by concatenating $b$ independent one-bit hashes:

$$h_{r_1,\dots,r_b}(x) = (h_{r_1}(x), \dots, h_{r_b}(x)).$$

For example, you can pick $b$ random hyperplanes; then the $i$th bit of the hash will indicate where the point falls relative to the $i$th hyperplane.

This avoids the need to invent new LSH functions.

• Thanks for your answer! So what you're suggesting would give me b different binary values. Are you saying I should then concatenate them into an integer represented in binary? I should clarify - I chose the argmax technique because it allows me to compute gradients with respect to the LSH. I'm trying to solve a weird optimization problem. Jan 2 '18 at 16:26