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.

The usual formula for euclidean distance that everybody uses is

$$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$

Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical precision.

There is an obviously equivalent formula:

$$d(x,y):= c \sqrt{\sum \left(\frac{x_i - y_i}{c}\right)^2}$$

Where it seems to be a common practise to choose $c = \max_i |x_i - y_i|$.

For 2d, this simplifies to a formula of the form: $d(x,y):= c \sqrt{1 + \frac{b}{c}^2}$

Some questions here:

  1. How big is the gain in precision of doing this, in particular for high dimensionalities?
  2. How much does it increate computational costs?
  3. Is this choice of $c$ optimal?
  4. To compute $c$, this needs two passes over the data. However, it should be possible in a single pass, by starting with $c_0=1$, and then adjusting it when necessary for optimal precision.

    E.g. let $c_0=1$, $c_i=\max_{j\leq i} |x_i-y_i|$. Then $$S_i:=\sum_{j\leq i} \left(\frac{x_i - y_i}{c_i}\right)^2 = \sum_{j\leq i-1} \left(\frac{x_i - y_i}{c_{i-1}}\right)^2 \cdot \frac{c_{i-1}^2}{c_i^2}+\left(\frac{x_i - y_i}{c_i}\right)^2 = S_{i-1} \cdot \left(\frac{c_{i-1}}{c_i}\right)^2+\left(\frac{x_i - y_i}{c_i}\right)^2$$ This should allow single-pass computation of this formula, right?

Any comments in particular on the computational cost and precision benefits of computing Euclidean distance this way? Why is everybody using the naive way, is the gain in precision too small for low dimensionality and the associated computational cost too high?

P.S. At least to my understanding, the usual formula should be precise up to the value range of sqrt(Double.MAX_VALUE) to sqrt(Double.MIN_NORMAL), which covers around e+-154, at most divided by the dimensionality - so even for 1000 dimensions, that should be fine for most uses of a distance function ...

share|improve this question
add comment

2 Answers 2

I'm no numerics expert, but the only advantage you can possibly get from the rescaling is to avoid arithmetic overflow/underflow if the input values are extreme. If the straightforward formula can be evaluated without overflow or underflow, it is no less precise than your embellished one.

In particular, if (a) you're doing the arithmetic in double precision, (b) you know that the true result cannot be larger than googol, and (c) you're willing to have the result be too small when the true result is less than a googolth, then bothering with rescaling will bring you no benefits.

General-purpose libraries typically cannot afford the last two assumptions, so they do need to rescale. On the other hand, one situation where these assumptions are guaranteed to be true is if the input coordinates are given as single precision floats (which can represent neither googol nor googolth).

If you do rescale, be sure to pick a $c$ that is a power of 2; then the scaling operations can be done with no rounding error (and possibly faster, if implemented with, say, ldexp() in C).

share|improve this answer
    
That is essentially why I asked. To my understanding, it should not make a big difference while the value range is inbetween of sqrt(Double.MAX_VALUE) and sqrt(Double.MIN_NORMAL), which covers around e+-154. –  Anony-Mousse Jan 25 '12 at 18:02
add comment

I'm using the naive way, and I found that the loss of precision is significant for small distances (like between points (1,8) and (16,3)) for instance. The error is very significant, try for yourself.

share|improve this answer
    
I don't get any precision problems on this example. –  Anony-Mousse Feb 26 at 9:03
    
I was implementing it incorrectly. Sorry. –  felipead Mar 8 at 4:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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