What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
[1] https://en.wikipedia.org/wiki/Curse_of_dimensionality
[2] http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/...
The M-Tree is one of my favorite indexes. It works with data that's embedded in infinite dimensional spaces (sometimes; it's bumping up against an impossibility result that's sketched in a sibling comment).
Even though almost every all pairs of points are almost a full diameter away from each other, they are also almost all almost orthogonal (i.e. the angle they make with the center of the sphere is very close to 90 degrees).
What I have just thought about though, is what points would be exactly diameter/2 distance away from that point? If you have a circle, you might think it would be the points that form a 90 degree triangle, but that is not the case, those points would be sqrt(2)*radius distance away.
So while it is obvious to me that it is not diameter/2, it is not obvious to me why it would be diameter either, or how larger n converges it closer to the diameter or some other fixed number.
x1^2 + x2^2 + … + xn^2 = 1.
D = (x1-1)^2 + x2^2 + … + xn^2
x1^2 = 1 - x2^2 - x3^2 - … - xn^2
But we can be more mathematical about it. Our (very reasonable) assumption is that the volume of a n-dimensional disk is proportional to the nth power of its radius. The third equation shows that x1 is going to be big (meaning the distance to the chosen point above is not so close to the diameter) if a corresponding[1] point on the n-disk is close to the middle. But the distance from the origin, R, of a random point in the n-disk is distributed with pdf proportional to p(r) = r^n for r in [0,1]. So the cdf is just r^(n+1) and E[x1^2] = 1 - E[R] = 1 - (n+1)/(n+2), which tends to 0 as n grows.
Therefore we get E[D] = E[(1-x1)^2] + 1 - E[x1^2] which tends to 2 as n grows large.
[1] the correspondence is that if I give you a point on a disk, you can turn it into a point on a sphere by flipping a coin to decide if it goes in the upper or lower hemisphere and then projecting up or down perpendicular to the disk from the point onto the sphere. But thinking a little more, I’m not sure this preserves the metric as it favours points on the sphere that correspond to the middle parts of the disk. So I think the actual expected value of x1 should be smaller.
D = (x₁-1)² + (x₂² + … + xₙ²)
Since we know that ∑xₙ²=1, and that x₁² is almost 0, then we also know that ∑xₙ² - x₁² is almost 1, which is the 2nd half of the above expression for D. So the average distance converges to "almost 1 + almost 1", which "almost 2", which is the diameter.
So exactly 1 gives a distance of 1, but almost 1 + almost 1 gives a distance of almost square root of 2.
I'm not sure it will. x1 is chosen randomly in the -1..1 interval. I dont see how the million other dimensions would force it to stick to 0. Those N other dimensions shrink the stddev(xi) by sqrt(N), though.
D^2 = (1 - x1)^2 + (1 - x1^2) = 2 - 2x1
We know that x1 is 0 on average, but its distribution is restricted by the fact that we choose a random point on the n-sphere. So what's the probability of that random point falling into a thin stripe where abs(x1) < eps? And how does this probability behave for large n?
This eps-stripe is basically the (n-1)-sphere of width eps, so the stripe's area A(n)=eps•S(n-1), and so our probability p=eps•S(n-1)/S(n).
The "magical" property of n-spheres is that their area grows at first, reaches maximum in 7 dimensions and then falls off rapidly to zero. Using formulas from wikipedia, I get: p = eps•(n/4)^(n/2) for large n.
In other words, the distribution of x1 approaches the look of the delta function at the n^n pace and for all practical matters, D=sqrt(2) with high precision for n > 10.
Where
On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
Distance = square root of ((X1 - X2) ^ 2 + (Y1 - Y2) ^2 + …). So D = square root of ((~0-0)^2 + (~0-0)^2 + (~0-0)^2 + … ), which is equal to 1 by definition of the unit high dimensional sphere.
So distance from (1,0,0,0 …) to (~0, ~0, ~0, …) = square root of ((~0-1)^2 + (~0-0)^2 + (~0-0)^2 + … ) ~= square root of 2.
d(x,y) = 0 if x == y; 1 otherwise
Then all points are distance one apart. It's been proven that, as dimensionality increases, normal euclidian distance over uniform point clouds rapidly converges to have the same behavior as the equality metric.
The proof relies on the information gained by performing pairwise distance calculations.
In the example distance function I gave, there is zero information gained if you plug in two points that are known to be non-equal.
The information gained from evaluating the Euclidian distance function converges to zero as the dimensionality of the data set increases.
(Note: This does not hold for low dimensional data that's been embedded in a higher dimensional space.)
Edit: Misread your comment. Yes, everything ends up being the same distance apart. More precisely, the ratio of mean distance / stddev distance tends to infinity. The intrinsic dimensionality of the data is monotonic w.r.t. that ratio.
Consider the origin (0,0,0, …) to a random point on the sphere (~0, ~0, ~0, …). So Distance from origin = square root of ((~0-0)^2 + (~0-0)^2 + (~0-0)^2 + … ), which sums to 1 by definition of the unit high dimensional sphere.
Then plug in 1 vs 0 in the first place because we care about (1,0,0,0 …) and you get the correct answer = square root of ((~0-1)^2 + (~0-0)^2 + (~0-0)^2 + … ) ~= square root of 2.
Edited to fix typo and add clarity.