Exercise: angle between high-dimensional unit vectors


I stumbled across this trigonometric formula for high-dimensional vector in the (d-1)-sphere while proof-reading the last two LSH papers (“beyond LSH”, and “optimal data-dependent LSH”). It is an interesting formula because it present the angle between the points fully characterized by the distance between the points.

So, let’s do it.

Suppose you have two high-dimensional vectors u,v \in S^{d-1}=\{x \in R^d | ||x|| = 1\} [unitary (d-1)-sphere]. They form an angle of \alpha. Take the center of the sphere and the difference between the vectors, so we obtain a triangle with two edges length 1 and one edge length ||u-v|| (the angle \alpha is on the opposite side of the edge u-v). If we take the bisector of the angle \alpha we obtain two new similar right triangles with edge lenghts 1, c and \frac{||u-v||}{2} (see the above photo) and angle \alpha/2.

Now we have this two relations:

tan^2(\frac{\alpha}{2}) = \frac{||u-v||^2}{4} \frac{1}{c^2}

Which gives us \frac{1}{c^2}=\frac{4}{4-||u-v||^2} and tan^2(\frac{\alpha}{2}) = \frac{||u-v||^2}{4-||u-v||^2}

Since the only information to characterize the angle is the distance between the points, this could be heuristically generalized to metric spaces (keeping aware that the proof doesn’t hold, neither the notion of “angle” between vectors).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s