Definition of normalized Euclidean distance

Question

Recently I have started looking for the definition of normalized Euclidean distance between two real vectors $u$ and $v$. So far, I have discovered two apparently unrelated definitions:

http://en.wikipedia.org/wiki/Mahalanobis_distance

and

http://reference.wolfram.com/language/ref/NormalizedSquaredEuclideanDistance.html

I am familiar with the context of the Wikipedia definition. However, I am yet to discover any context for the Wolfram.com definition:

NormalizedSquaredEuclideanDistance[u,v] is equivalent to 1/2*Norm[(u-Mean[u])-(v-Mean[v])]^2/(Norm[u-Mean[u]]^2+Norm[v-Mean[v]]^2)

$$ NED^2[u,v] = 0.5 \frac{ Var[u-v] }{ Var[u] + Var[v] }$$

=========================================================================

The intuitive meaning of this definition is not very clear. Any help on this will be appreciated.

Update:

I find that the following intuitive explanation for the Wolfram.com definition is given here

I am repeating that below:

Note that it is a DistanceFunction option for ImageDistance. Maybe that helps some to see the context where it is used.

The relation to SquaredEuclideanDistance is:

NormalizedSquaredEuclideanDistance[x, y] == (1/2) SquaredEuclideanDistance[x - Mean[x], y - Mean[y]]/ (Norm[x - Mean[x]]^2 + Norm[y - Mean[y]]^2)

So we see it is "normalized" "squared euclidean distance" between the "difference of each vector with its mean"...

What is the meaning about 1/2 at the beggining of the formula?

The 1/2 is just there such that the answer is bounded between 0 and 1, rather than 0 and 2.

Answer 1

The normalized squared euclidean distance gives the squared distance between two vectors where there lengths have been scaled to have unit norm. This is helpful when the direction of the vector is meaningful but the magnitude is not. It's not related to Mahalanobis distance.

Answer 2

The weighted Minkowski distance of order $q$ between two real vectors $u, v \in \mathbb{R}^n$ is given by

$$d^{(q)} (u, v) = \left(\sum_{i=1}^n w_i (u_i - v_i)^q \right)^\frac{1}{q}$$

[See equation $3.1.7$, Clustering Methodology for Symbolic Data By Lynne Billard, Edwin Diday (2019)]

If we choose $w_i = \frac{1}{n}$ and $q = 2$, we have the so called "normalized Euclidean distance" between $u$ and $v$

$$d_{NE}^2(u, v) = \frac{1}{n} \sum_{i=1}^n \left(u_i - v_i \right)^2$$

Unfortunately, the above definition does not have nice properties...

Another definition given at Wolfram.com has one nice property; $d_W$ is always between $0$ and $1$

NormalizedSquaredEuclideanDistance[u,v] is equivalent to 1/2*Norm[(u-Mean[u])-(v-Mean[v])]^2/(Norm[u-Mean[u]]^2+Norm[v-Mean[v]]^2)

For computational purposes, I simplified the definitions given above:

$$d_{NE}^2(u, v) = \mathrm{Var}(u-v) + (\bar{u} - \bar{v})^2$$

$$NED^2(u, v) = d_W ^2(u, v) = \frac{1}{2}\frac{\mathrm{Var}(u-v)}{\mathrm{Var}(u) + \mathrm{Var}(v)}$$ where $\mathrm{Var}(x) = \displaystyle \frac{1}{n}\sum_{i=1}^n (x_i - \bar{x})^2$ and $\bar{x} = \frac{\sum_{i=1}^n x_i}{n}$

A few properties/special cases:

If (i) $||u||_2 = ||v||_2 = 1$, i.e., $\sum_{i=1}^n u_i^2 = \sum_{i=1}^n v_i^2 = 1$

and

(ii) $\bar{u} = \bar{v} = 0$, i.e., $\sum_{i=1}^n u_i = \sum_{i=1}^n v_i = 0$

then

(A) $\mathrm{Var}(u) = \mathrm{Var}(v) = \frac{1}{n}$, $\mathrm{Cov}(u, v) = \frac{1}{n}\sum_{i=1}^n u_i v_i$ and $\rho(u,v) = \sum_{i=1}^n u_i v_i = \cos \theta$

where $\theta$ is the angle between the vectors $u$ and $v$

(B) $$d_{NE}^2(u, v) = \frac{2}{n}(1 - \cos \theta)$$

(C) $$d_W^2 (u, v) = \frac{1}{2}(1 - \cos \theta)$$

Discussion:

Suppose we define the following distance measure $d_E^2(u, v)$ between the vectors $u, v \in \mathbb{R^n}$

$$d_E^2(u, v) = \frac{\sum_{i=1}^n (u_i - v_i)^2}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2}$$

This measure lies between $0$ and $\sqrt{2}$

The Wolfram.com definition is closely related to the above. Instead of $u$ and $v$, it considers the mean centered version of the above definition and adds a factor of $\frac{1}{2}$ so that the value lies between $0$ and $1$

Proof: $$\sum_{i=1}^n (u_i - v_i)^2 \geq 0 \implies \frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2} \leq 1$$

$$\sum_{i=1}^n (u_i + v_i)^2 \geq 0 \implies -1 \leq \frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2}$$

Combining the above two inequalities:

$$-1 \leq \frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2} \leq 1$$

Or, $$-1 \leq -\frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2} \leq 1$$

Or, $$0 \leq 1-\frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2} \leq 2$$

Or, $$0 \leq \frac{1}{2}\left( 1-\frac{2\sum_{i=1}^n u_i v_i}{\sum_{i=1}^n u_i^2 + \sum_{i=1}^n v_i^2} \right)\leq 1$$

Or, $$0 \leq \frac{1}{2} d_E^2(u, v)\leq 1$$

Or, $$0 \leq d_E(u, v)\leq \sqrt{2}$$

How do we prove that $$0 \leq d_W ^2(u, v) = \frac{1}{2}\frac{\mathrm{Var}(u-v)}{\mathrm{Var}(u) + \mathrm{Var}(v)} \leq 1$$

Proof:

We are required to prove that (TPT)

$$0 \leq \frac{1}{2}\frac{\mathrm{Var}(u-v)}{\mathrm{Var}(u) + \mathrm{Var}(v)} \leq 1$$

i.e., TPT $$0 \leq \mathrm{Var}(u-v) \leq 2(\mathrm{Var}(u) + \mathrm{Var}(v))$$

Now $\mathrm{Var}(u-v) \geq 0$ since variance is always non-negative.

We need TPT $$\mathrm{Var}(u-v) \leq 2(\mathrm{Var}(u) + \mathrm{Var}(v))$$

i.e., TPT $$\mathrm{Var}(u-v) = \mathrm{Var}(u) + \mathrm{Var}(v) - 2 \mathrm{Cov}(u, v) \leq 2(\mathrm{Var}(u) + \mathrm{Var}(v))$$

i.e., TPT $$\mathrm{Var}(u) + \mathrm{Var}(v) + 2 \mathrm{Cov}(u, v) \geq 0$$

i.e., TPT $$\mathrm{Var}(u+v) \geq 0$$ which is always true since variance is always non-negative.

Answer 3

Here is one way of thinking about the Normalised Squared Euclidean Distance $NED^2$, defined as $$NED^2(u,v) = 0.5 \frac{ \text{Var}(u-v) }{ \text{Var}(u) + \text{Var}(v) }$$ for two vectors $u,v\in\mathbb{R}^k$.

This definition does not appear very much in the scientific literature. I can see at least two problems with this definition. First, it does not make sense in the case where the dimension $k=1$ because all the variances are zero in this case. Secondly, if both $u$ and $v$ are constant, i.e. $u_i=c$, $v_i=c'$ for all $i$, then the distance is undefined regardless of $k$. In fact, this second scenario covers the first as a special case.

One principle by which to handle these problems with the definition is to consider the underlying context. Although not well used in the literature, I suspect that $NED^2$ was originally defined in the context of image processing of the kind described in this question. Here, an image is regarded as a vector of pixel intensity values, so we may think of $u$ and $v$ as representing images we wish to compare, with $k$ being the number of pixels in each image. Frequently, in image processing, we are only interested in relative spatial variation in pixel intensities rather than the absolute values of the pixel intensities, which motivates the use of a distance measure which 'de-means' the pixel intensity vectors. Two images which are 'shifts' of each other, so that $u_i=v_i+c$ for all $i$, are essentially 'the same' for many purposes. So, roughly speaking, $NED^2$ quantifies the variation in the difference image $u-v$, normalised by the sum of the variation apparent in the two original images $u$,$v$.

With this in mind, let's go back to the problem with the definition of $NED^2$. If $u_i=c$, $v_i=c'$ for all $i$, then $NED^2$ is undefined. However, the images are just shifts of one another, so should be regarded as essentially the same. Therefore, in the context of image processing I suggest that $NED^2$ should be set to zero in all cases where it is apparently undefined.

How should you proceed if you are working in in a different context or application area? I can see three possible outcomes:

1. The same principles apply as for image processing, so you define $NED^2$ to be zero in all undefined cases.
2. The context motivates an alternative definition of $NED^2$ in the undefined cases e.g. the one you have proposed in the above question.
3. The problems with the definition motivate you to reject $NED^2$ as a useful distance measure, so you look for other measures instead.

Which of these three options applies will depend on your problem and your reasons for using $NED^2$.

Additional details: more formally, $NED^2$ is really a distance measure on the quotient vector space $\mathbb{R}^k/\mathbb{R}\mathbf{1}$ where $\mathbf{1}$ denotes the vector $(1,1,\cdots,1)$. This is just a consequence of $NED^2$ being invariant to adding multiples of $\mathbf{1}$ to either $u$ or $v$. On the quotient space $NED^2$ is defined everywhere except at $([\mathbf{0}],[\mathbf{0}])$, where $\mathbf{0}$ is the zero vector and $[\mathbf{0}]=\mathbb{R}\mathbf{1}$ is the equivalence class of the zero vector. In this setting it seems very logical to define $NED^2$ to be zero at this single undefined point.

Answer 4

I believe this is the correct implementation in pytorch (should be easy to translate to numpy etc):

import torch.nn as nn


def ned(x1, x2, dim=1, eps=1e-8):
    ned_2 = 0.5 * ((x1 - x2).var(dim=dim) / (x1.var(dim=dim) + x2.var(dim=dim) + eps))
    return ned_2 ** 0.5

def nes(x1, x2, dim=1, eps=1e-8):
    return 1 - ned(x1, x2, dim, eps)

dim = 1  # apply cosine accross the second dimension/feature dimension

k = 4  # number of examples
d = 8  # dimension of feature space
x1 = torch.randn(k, d)
x2 = x1 * 3
print(f'x1 = {x1.size()}')
ned_tensor = ned(x1, x2, dim=dim)
print(ned_tensor)
print(ned_tensor.size())
print(nes(x1, x2, dim=dim))

output:

x1 = torch.Size([4, 8])
tensor([0.4472, 0.4472, 0.4472, 0.4472])
torch.Size([4])
tensor([0.5528, 0.5528, 0.5528, 0.5528])

feel free to comment if you see anything wrong.

---

Related:

• https://discuss.pytorch.org/t/how-does-one-compute-the-normalized-euclidean-distance-similarity-in-a-numerically-stable-way-in-a-vectorized-way-in-pytorch/110829
• https://github.com/pytorch/pytorch/issues/52005
• Definition of normalized Euclidean distance

---

Update: Edge cases taken care of

def ned_torch(x1: torch.Tensor, x2: torch.Tensor, dim=1, eps=1e-8) -> torch.Tensor:
    """
    Normalized eucledian distance in pytorch.

    Cases:
        1. For comparison of two vecs directly make sure vecs are of size [B] e.g. when using nes as a loss function.
            in this case each number is not considered a representation but a number and B is the entire vector to
            compare x1 and x2.
        2. For comparison of two batch of representation of size 1D (e.g. scores) make sure it's of shape [B, 1].
            In this case each number *is* the representation of the example. Thus a collection of reps
            [B, 1] is mapped to a rep of the same size [B, 1]. Note usually D does decrease since reps are not of size 1
            (see case 3)
        3. For the rest specify the dimension. Common use case [B, D] -> [B, 1] for comparing two set of
            activations of size D. In the case when D=1 then we have [B, 1] -> [B, 1]. If you meant x1, x2 [D, 1] to be
            two vectors of size D to be compare feed them with shape [D].

    https://discuss.pytorch.org/t/how-does-one-compute-the-normalized-euclidean-distance-similarity-in-a-numerically-stable-way-in-a-vectorized-way-in-pytorch/110829
    https://stats.stackexchange.com/questions/136232/definition-of-normalized-euclidean-distance/498753?noredirect=1#comment937825_498753
    """
    # to compute ned for two individual vectors e.g to compute a loss (NOT BATCHES/COLLECTIONS of vectorsc)
    if len(x1.size()) == 1:
        # [K] -> [1]
        ned_2 = 0.5 * ((x1 - x2).var() / (x1.var() + x2.var() + eps))
    # if the input is a (row) vector e.g. when comparing two batches of acts of D=1 like with scores right before sf
    elif x1.size() == torch.Size([x1.size(0), 1]):  # note this special case is needed since var over dim=1 is nan (1 value has no variance).
        # [B, 1] -> [B]
        ned_2 = 0.5 * ((x1 - x2)**2 / (x1**2 + x2**2 + eps)).squeeze()  # Squeeze important to be consistent with .var, otherwise tensors of different sizes come out without the user expecting it
    # common case is if input is a batch
    else:
        # e.g. [B, D] -> [B]
        ned_2 = 0.5 * ((x1 - x2).var(dim=dim) / (x1.var(dim=dim) + x2.var(dim=dim) + eps))
    return ned_2 ** 0.5

def nes_torch(x1, x2, dim=1, eps=1e-8):
    return 1 - ned_torch(x1, x2, dim, eps)

def nes_torch(x1, x2, dim=1, eps=1e-8):
    return 1 - ned_torch(x1, x2, dim, eps)

repo: https://github.com/brando90/Normalized-Eucledian-Distance-and-Similarity