1. ## Ordering proof?

Given unit vectors $\displaystyle q$ and $\displaystyle d_i$, i=1, 2, 3, ...,
$\displaystyle q, d_i \in \mathbb{R}^n$
and we compute $\displaystyle q\cdot d_i$ and the L2 distance between them, $\displaystyle |q-d_i|^2=\sum_{j=1}^n (q_i-d_{ij})^2$, and we were to order the $\displaystyle d_i$'s in increasing order of those computations, show that the relative orders of $\displaystyle d_i$ would be the same for both cases (i.e. the inner product and L2-norm).

(This is paraphrased from a problem in a non-math book)
Any tips?

1. You're confusing your notation there. You've got $\displaystyle d_{i}$ for the ith vector, but also for the ith component of one of those vectors. Better to write $\displaystyle (d_{i})_{j}$ for the jth component of the ith vector, and sum over j in the $\displaystyle L^{2}$ norm.

2. I'm a bit surprised at the result. I would have expected the order to reverse:
$\displaystyle |q-d_{i}|^{2}=(q-d_{i})\cdot(q-d_{i})=|q|^{2}-2q\cdot d_{i}+|d_{i}|^{2}=2-2q\cdot d_{i}$.

That last step is valid because everything in sight is a unit vector. So, in comparing $\displaystyle q\cdot d_{i}$ with the $\displaystyle L^{2}$ norm of the difference, you've got a sign reversal. Hence, I would expect the order to reverse.

3. Thanks - about the notation, that's a result of me editing in the d_i at the last minute, I forgot to fix the sum

The result does indeed strange; Here's what the question said:

4. Ok, you're going to have to help me out, here, please. What are "cosine similarities"?

5. That's just the cos(theta) = a.b/|a||b|, but because |a|=|b|=1 we can ignore it. So $\displaystyle q\cdot d_i$ in our case.

6. Well, if that's the case, I don't buy it. Let's take the 2-dimensional case. Let $\displaystyle \vec{q}=\{1,0\}$, $\displaystyle \vec{d}_{1}=\{1,0\}$, $\displaystyle \vec{d}_{2}=\{0,1\}$, and $\displaystyle \vec{d}_{3}=\{-1,0\}$.

Then we have the following ordering for Euclidean distance (least to greatest):

$\displaystyle |\vec{q}-\vec{d}_{1}|=0$
$\displaystyle |\vec{q}-\vec{d}_{2}|=\sqrt{2}$
$\displaystyle |\vec{q}-\vec{d}_{3}|=2$.

Now, we compute the dot products:

$\displaystyle \vec{q}\cdot\vec{d}_{1}=1$
$\displaystyle \vec{q}\cdot\vec{d}_{2}=0$
$\displaystyle \vec{q}\cdot\vec{d}_{3}=-1$.

The order is reversed, like I thought it would be.

7. Thanks a lot!

Would it make a difference if the numbers in the vectors were nonnegative?

8. No, it wouldn't. Think about it. All the vectors lie on the unit sphere. If you think of the d_i vector tips as getting farther and farther away from the q tip (pun intended), then the amount of d_i that is going in the same direction as q is getting smaller (this is what the dot product is measuring: the projection either of d_i onto q, or of q onto d_i). This is true, even if, in my example, the x component of the d_i's never goes negative.