Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Euclidean distance is a measure that may be used to compute the similarity between two vectors. Given a query $q$ and documents $d_1, \ldots, d_n$, we may rank the documents $\mathcal{D} = \{d_k\}_{k=1}^n$ in the increasing order of Euclidean distance from $q$.

Prove that if $q$ and the document vectors $\mathcal{D}$ are all normalized to unit vectors, then the rank ordering produced by Euclidean distance is identical to that produced by cosine similarity.

share|improve this question

put on hold as off-topic by Thursday, Mark Fantini, Claude Leibovici, studiosus, Jean-Claude Arbaut Aug 27 at 5:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Thursday, Mark Fantini, Claude Leibovici, studiosus, Jean-Claude Arbaut
If this question can be reworded to fit the rules in the help center, please edit the question.

    
What is a cosine similarity? Computing $\dfrac{\vec{x}\cdot \vec{y}}{\|\vec{x}\| \|\vec{y}\|}$? –  gt6989b Mar 20 '13 at 17:10
1  
@gt6989b Yes en.wikipedia.org/wiki/Cosine_similarity#Definition –  benji_r Mar 20 '13 at 17:11

1 Answer 1

Doesn't seem true to me. Take $\mathcal{D}=\{(1,0), (0,1)\}$ and $q = (a,b)$ on the unit circle. Then, the cosine similarity would result in $q \cdot d_1 = a$ and $q \cdot d_2 = b$. Euclidean distance (we consider the square of the actual distance, it doesn't alter comparisons), however, would have $(a-1)^2+b^2$ and $a^2 + (b-1)^2$.

Note that $$ \begin{split} (a-1)^2+b^2 &< a^2 + (b-1)^2 \\ a^2 -2a + 1+b^2 &< a^2 + b^2 -2b +1 \\ -2a &< -2b \\ b &< a \end{split} $$

So the distance ranking orders $d_1 < d_2$ iff the cosine ranking orders $d_2 < d_1$.

It seems, this is the counterexample, since they produce a different ordering. Or am I not understanding something?

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.