0
$\begingroup$

I am trying to simplify the euclidean distance function to the reduce computation time of some code. I am not interested on the numerical result of the distance but rather on which is the closest vector, but I do not care by how much (I hope that makes sense).

The best approximation I have found so far is the Manhattan distance. However, I would like to know if there is any established method of quantifying the error incurred by using the Manhattan distance.

What I had in mind is generating random vectors of the same dimension I use and quantifying the percentage of times the result of the comparison is different when using euclidean distance than Manhattan, as I am only interested in the result of the comparison but not on the value of the distance itself.

Many thanks!

$\endgroup$
1
  • $\begingroup$ If you're only interrested in comparing distances then you can simply skip taking the square root in the end - that is calculating the distance squared instead of the distance. Often it's taking the square root that is the most expensive operation, multiplication (squaring) is often a quite cheap operation these days. $\endgroup$ – skyking Jun 12 '17 at 10:53
1
$\begingroup$

The manhattan distance between $P$ and $Q$ (in $\Bbb R^n$) is no more than $\sqrt{n}$ times the Euclidean distance.

Proof: Consider all unit vectors (in Euclidean distance). For each, compute the Manhattan distance. Maximize this function to find that the point $$ (\frac{1}{\sqrt{n}}, \ldots, \frac{1}{\sqrt{n}}) $$ is a maximizer. Compute its Manhatten length: $\sqrt{n}$. Done.

Post-comment addition

Oh...wait. I now see what you're asking. The answer is "It's arbitrarily bad."

For instance, in the plane, consider the $K$ points $$ P_n = \frac{K-n}{K} (1, 0) + \frac{n}{K}(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}-u),$$ where $u$ is some small positive number like $0.1$.

These lie on a line from $(1,0)$ to $S = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}-u)$, which is a point just inside the unit circle. So in Euclidean distance, they're getting shorter and shorter.

Their manhattan distances (to the origin) are \begin{align} d_n &= \frac{K-n}{K}+ \frac{n}{K\sqrt{2}} + \frac{n}{K} (\frac{1}{\sqrt{2}} - u)\\ &= 1 - \frac{n}{K}+ 2\frac{n}{K\sqrt{2}} - \frac{n}{K}u \\ &= 1 - \frac{n}{K}+ \frac{n}{K}\sqrt{2} - \frac{n}{K}u \\ &\approx 1 + 0.414 \frac{n}{K} - \frac{n}{K}u\\ &= 1 + (0.414-u) \frac{n}{K} \end{align}

If we pick $u < 0.414$, the it's easy to see that these distances are increasing with $n$. So a sequence that's decreasing in its distance to the origin (in Euclidean) can be increaasing in distance-to-origin in Manhattan -- a complete reversal of the comparisons between any two distances.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer John. However, I do not quite understand how this lemma helps me quantify the loss of accuracy I create by using Manhattan as opposed to euclidean. This provides an upper bound for Manhattan in terms of euclidean, but says nothing about the error, right? Sorry If I misunderstood your point. $\endgroup$ – Ruben Jun 12 '17 at 10:32
  • $\begingroup$ Perhaps I don;t know what you mean by "error". If you mean the difference $$d_m(P, Q) - d_e(P, Q),$$ then my example shows that this difference can be as large as $(\sqrt{n}-1)d_e(P, Q)$. In particular, the farther apart $P$ and $Q$ are (by Euclidean standards), the greater the error you may get by pretending that the distance is the Euclidean distance. $\endgroup$ – John Hughes Jun 12 '17 at 10:36
  • $\begingroup$ Thanks again John. Perhaps I wasn't clear enough on the question. I am not interested in the value of the distance itself. Say I have a vector a, and two vectors b and c. Then, I would like to know which of b or c is closer to a but I do not care about the number just about which is closer. As I understand it, error would be the % of time that the Euclidean and Manhattan distance do not agree, in which case the result would be wrong if Manhattan was used in place of euclidean. As a question, when is a closer to b using euclidean but closer to c using Manhattan? $\endgroup$ – Ruben Jun 12 '17 at 10:42
  • $\begingroup$ See my post-comment addition. In the example I gave, I've fixed $a$ to be the origin. $\endgroup$ – John Hughes Jun 12 '17 at 10:48
  • 1
    $\begingroup$ You could do that, but what would it show? It'd show how often the comparison swaps...but only for uniformly distributed points. But in real data, "uniformity" is amazingly rare, so for whatever application you're doing, chances are your error rate will be much larger. (BTW, you could also just think about the geometry of the situation and compute this difference without running the tests at all...which might lead you to some insight.) $\endgroup$ – John Hughes Jun 12 '17 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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