10
$\begingroup$

This is cited very often when mentioning the curse of dimensionality and goes

(righthand formula called relative contrast)

$$ \lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]} \right) = 0, \text{then}: \frac{D_{\max^{k}_{d}} - D_{\min^{k}_{d}}}{D_{\min^{k}_{d}}} \rightarrow 0$$

The result of the theorem shows that the difference between the maximum and minimum distances to a given query point does not increase as fast as the nearest distance to any point in high dimensional space. This makes a proximity query meaningless and unstable because there is poor discrimination between the nearest and furthest neighbor.

link

Yet if one actually tries out calculating the relative contrast for sample values, meaning one takes a vector containing very small values and calculates the distance to the zero vector and does the same for a vector containing much larger values, and one then compares the values for a dimension of 3 and a dimension $10^9$ times bigger, one will see that, while the ratio does decrease, the change is so vanishingly small as to be irrelevant for the number of dimensions actually used in practice (or does anyone know anyone working with data with dimensions the size of Graham's number - which I would guess is the size needed for the effect described the paper to actually be relevant - I think not).

As previously mentioned, this theorem is very often cited to support the statement that measuring proximity based on euclidean space is a poor strategy in a high dimensional space, the authors say so themselves, and yet the proposed behaviour does not actually take place, making me think this theorem has been used in a misleading fashion.

Example: with d the dimension

a=np.ones((d,)) / 1e5
b=np.ones((d,)) * 1e5
dmin,dmax=norm(a), norm(b)
(dmax-dmin)/dmin

for d=3
9999999999.0
for d=1e8
9999999998.9996738

And with 1e1 instead of 1e5 (let's say the data is normalized)
for d=3
99.0
for d=1e8
98.999999999989527

$\endgroup$
  • 2
    $\begingroup$ How did you obtain a sample of data in dimension $3 + 10^9$? Are you perhaps confusing "dimension" with "scale"? $\endgroup$ – whuber Nov 7 '17 at 18:40
  • 2
    $\begingroup$ Did you check the condition on the variance? $\endgroup$ – Aksakal Nov 7 '17 at 18:53
8
$\begingroup$

No, the theorem is not misleading. It can certainly be applied incorrectly, but that's true for any theorem.

Here's simple MATLAB script to demonstrate how it works:

xd = randn(1e5,10000);
%%
cols = [1,10,100,1000,10000];
for c = cols
    xdt = table(xd(:,1:c));
    res = table2array(rowfun(@norm,xdt));
    mr = mean(res);
    res1 = var(res/mr);
    res2 = (max(res) - min(res))/min(res);
    fprintf('res1: %f, res2: %f\n',res1,res2)
end

The OUTPUT:

res1: 0.568701, res2: 2562257.458668
res1: 0.051314, res2: 9.580602
res1: 0.005021, res2: 0.911065
res1: 0.000504, res2: 0.221981
res1: 0.000050, res2: 0.063720

In my code res1 and res2 are the two expressions in your equation from the paper: one for variance, and the second one for the contrast.

You can see how both go to zero as supposed to when dimensions go from 1 to 10,000.

$\endgroup$
  • $\begingroup$ Now I feel the question becomes, for what distributions from which X comes does the variance go to zero? $\endgroup$ – Nimitz14 Nov 7 '17 at 19:28
  • 2
    $\begingroup$ @Nimitz14 That would make an excellent question to ask in its own right. $\endgroup$ – Sycorax says Reinstate Monica Nov 7 '17 at 20:58
  • 3
    $\begingroup$ @Nimitz14 this theorem should not work for Cauchy, you can test it easily by replacing normal with student t(1). Otherwise, I think all regular distributions such as normal, uniform, beta etc. should be covered. $\endgroup$ – Aksakal Nov 7 '17 at 21:37

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.