# Locality-sensitive hashing random projection

I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that will be used for the random projection. So, in LSH for Cosine Similarity, the define the hash function $h_i(\vec{v}) = 1$ only if $\vec{r_i} \cdot \vec{v} \geq 0$ and $h_i(\vec{v}) = 0$ only if $\vec{r_i} \cdot \vec{v} < 0$. There are a lot of places that mention that this dot product of $\vec{v}$ and $\vec{r_i}$ means which side of the line (assuming a 2D dimension for instance) the point in question $\vec{v}$ is (negative for one side and positive for the other side), just like in the image below: However, to my understanding, what will give which side of the line where the point $\vec{v}$ is, is the dot product of the norm of the $\vec{r_i}$ (let's say that the norm is $\vec{n}$) and the vector $\vec{v}$, so the correct wouldn't be the equation $\vec{n_i} \cdot \vec{v}$ instead of $\vec{r_i} \cdot \vec{v}$ ?

## 1 Answer

No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).

• So, you're saying that in this case, the r is the the norm of the hyperplane ? Otherwise it doesn't makes sense for me. Because you can have positive dot product of two vectors even if the vector is above or below each other (so this dot product doesn't carries information on which side of the vector the point is). – Tarantula Aug 5 '16 at 2:00
• @Tarantula, no, I'm not saying that. Did you try a concrete example yet? Rather than continuing to say it doesn't make sense, try an example first. The line probably isn't where you think it is -- try an example and see where the resulting line falls. – D.W. Aug 5 '16 at 5:12
• Ok, I already did this. Let me be clear, we have the r = (4,4), v1 = (3,2) and v2 = (1,4). So, r * v1 = 20 and r * v2 = 20. Both v1 and v2 are on different sides of the vector r, and both results in 20 as the dot product with r. Still didn't get it. – Tarantula Aug 5 '16 at 13:28
• @Tarantula, draw a picture. Draw the line -- the set of points $v$ such that $v \cdot (4,4) = 0$. Try it. It's not where you think it is. Where you're going wrong is your talking about "on which side of the vector r"; that's not what is meant. Instead about "which side of the line" you're on, which is not the same thing. – D.W. Aug 5 '16 at 15:53
• @Tarantula, OK. Would you like to write an answer to your own question, to help others who might have the same confusion? – D.W. Aug 5 '16 at 15:59