8 ms·

> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all

> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.

deleted 5y ago
[deleted]
deleted 5y ago
[deleted]
aix1 5y ago
Not my area of expertise, but the quoted "fact" seems at best incompletely stated: surely for it to hold there must be some constraints on the number of points (likely as a function of the diameter)?
- Retric 5y ago
  It’s just wrong as stated, there is only one point a full diameter away from each point on a high dimensional sphere. Aka (1,0,0,0,0, …) maps to (-1,0,0,0,0, …) and nothing else. Just as (1,0) maps to (-1,0) on a unit circle and (1,0,0) maps to (-1,0,0) on a unit sphere. On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
  - bick_nyers 5y ago
    Euclidean distance calculations change based on number of dimensions, for example, in 3 dimensions it is sqrt(a^2+b^2+c^2).
    - Retric 5y ago
      Yes, that’s why it’s square root of 2. Consider the origin (0,0,0, …) to a random point on the sphere (~0, ~0, ~0, …). 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.
      - bick_nyers 5y ago
        Ahh ok, for some reason I was thinking (1,1,1) would be a valid point in this case
  - hedora 5y ago
    If the data points are in the space [0,1]^n, and your metric function is: 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.
  - dan-robertson 5y ago
    The fact should say that the expected distance between two random points tends to the diameter as the dimension increases. The intuition is that to be close you need to be close in a large number of coordinates and the law of large numbers (though coordinates aren’t independent) suggests that is unlikely. If you fix one point on a sphere (say (1,0,…,0)) then, for a high dimension, most points will not have any extreme values in coordinates and will look like (~0,~0,…,~0) where ~0 means something close to zero. But if we sum the squares of everything apart from the first we get 1 - (~0)^2 ~= 1, so the distance from our fixed point is (1 - ~0)^2 + sum_2^n (0 - ~0)^2 ~= 1 + 1 = 2.
    - Retric 5y ago
      You forgot the square root on distance formula. Distance = square root of ((X1 - X2) ^ 2 + (Y1 - Y2) ^2 + …). 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.
      - dan-robertson 5y ago
        Wow. Can’t believe I missed that.
- ravi-delia 5y ago
  It should be almost all points are almost a full diameter away. However it's still very striking, and an unintuitive fact about very high dimensional spheres.
- pfortuny 5y ago
  It is for VERY HUGE n, as siblings explain.
leto_ii 5y ago
I think it's something related to the curse of dimensionality [1] [2], basically just a property of high dimensional spaces (perhaps only certain kinds of spaces though). [1] https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality [2] http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/On_the_Surprising_Behavior_of_Distance_Metric_in_High_Dimensional_Space.pdf?sequence=1 http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/...
- hedora 5y ago
  The intrinsic dimensionality of a dataset is also relevant here. 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).
- bo1024 5y ago
  Yes. 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).
bick_nyers 5y ago
My initial intuition is telling me that it would be diameter/2, from the perspective of a single point, the closest points would be near zero distance away, and the furthest points would be on the opposite side, a full diameter away, and I am assuming that there are a lot of points in a uniform distribution. 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.
- adgjlsfhk1 5y ago
  I think the most intuitive way of thinking about this is sphere packing. Asking what percent of points are within distance d of an n-sphere of radius 1 is equivalent to asking what the ratio of volumes is. For d<1, the n-volume of a radius d sphere tends to 0 as n goes towards infinity, so that means almost all of the points are as far away as possible.
- dan-robertson 5y ago
  If you consider a point on the sphere it means choosing a bunch of xi such that: x1^2 + x2^2 + … + xn^2 = 1. Suppose wlog you pick (1,0,0,…,0). Then the distance from your point to a random point is: D = (x1-1)^2 + x2^2 + … + xn^2 And from the first equation we know: x1^2 = 1 - x2^2 - x3^2 - … - xn^2 Intuitionistically, your point will be far from a random point if x1 is close to zero, and x1 will be close to zero because everything is close to zero. 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.
bjourne 5y ago
It's just another way to state the https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality
grungegun 5y ago
For reference, see the book High Dimensional Probability by Vershynin. It's free online. See Theorem 3.1.1. It proves that a sub-gaussian random vector is in some sense close in norm to sqrt(n) where n is the number of dimensions. Most of these results are true up to multiplying by some unknown constant.

deleted 5y ago

[deleted]

deleted 5y ago

[deleted]

aix1 5y ago

Not my area of expertise, but the quoted "fact" seems at best incompletely stated: surely for it to hold there must be some constraints on the number of points (likely as a function of the diameter)?

Retric 5y ago
It’s just wrong as stated, there is only one point a full diameter away from each point on a high dimensional sphere. Aka (1,0,0,0,0, …) maps to (-1,0,0,0,0, …) and nothing else. Just as (1,0) maps to (-1,0) on a unit circle and (1,0,0) maps to (-1,0,0) on a unit sphere. On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
- bick_nyers 5y ago
  Euclidean distance calculations change based on number of dimensions, for example, in 3 dimensions it is sqrt(a^2+b^2+c^2).
  - Retric 5y ago
    Yes, that’s why it’s square root of 2. Consider the origin (0,0,0, …) to a random point on the sphere (~0, ~0, ~0, …). 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.
    - bick_nyers 5y ago
      Ahh ok, for some reason I was thinking (1,1,1) would be a valid point in this case
- hedora 5y ago
  If the data points are in the space [0,1]^n, and your metric function is: 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.
- dan-robertson 5y ago
  The fact should say that the expected distance between two random points tends to the diameter as the dimension increases. The intuition is that to be close you need to be close in a large number of coordinates and the law of large numbers (though coordinates aren’t independent) suggests that is unlikely. If you fix one point on a sphere (say (1,0,…,0)) then, for a high dimension, most points will not have any extreme values in coordinates and will look like (~0,~0,…,~0) where ~0 means something close to zero. But if we sum the squares of everything apart from the first we get 1 - (~0)^2 ~= 1, so the distance from our fixed point is (1 - ~0)^2 + sum_2^n (0 - ~0)^2 ~= 1 + 1 = 2.
  - Retric 5y ago
    You forgot the square root on distance formula. Distance = square root of ((X1 - X2) ^ 2 + (Y1 - Y2) ^2 + …). 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.
    - dan-robertson 5y ago
      Wow. Can’t believe I missed that.
ravi-delia 5y ago
It should be almost all points are almost a full diameter away. However it's still very striking, and an unintuitive fact about very high dimensional spheres.
pfortuny 5y ago
It is for VERY HUGE n, as siblings explain.

leto_ii 5y ago

I think it's something related to the curse of dimensionality [1] [2], basically just a property of high dimensional spaces (perhaps only certain kinds of spaces though). [1] https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality [2] http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/On_the_Surprising_Behavior_of_Distance_Metric_in_High_Dimensional_Space.pdf?sequence=1 http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/...

hedora 5y ago
The intrinsic dimensionality of a dataset is also relevant here. 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).
bo1024 5y ago
Yes. 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).

bick_nyers 5y ago

My initial intuition is telling me that it would be diameter/2, from the perspective of a single point, the closest points would be near zero distance away, and the furthest points would be on the opposite side, a full diameter away, and I am assuming that there are a lot of points in a uniform distribution. 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.

adgjlsfhk1 5y ago
I think the most intuitive way of thinking about this is sphere packing. Asking what percent of points are within distance d of an n-sphere of radius 1 is equivalent to asking what the ratio of volumes is. For d<1, the n-volume of a radius d sphere tends to 0 as n goes towards infinity, so that means almost all of the points are as far away as possible.
dan-robertson 5y ago
If you consider a point on the sphere it means choosing a bunch of xi such that: x1^2 + x2^2 + … + xn^2 = 1. Suppose wlog you pick (1,0,0,…,0). Then the distance from your point to a random point is: D = (x1-1)^2 + x2^2 + … + xn^2 And from the first equation we know: x1^2 = 1 - x2^2 - x3^2 - … - xn^2 Intuitionistically, your point will be far from a random point if x1 is close to zero, and x1 will be close to zero because everything is close to zero. 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.

bjourne 5y ago

It's just another way to state the https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality

grungegun 5y ago

For reference, see the book High Dimensional Probability by Vershynin. It's free online. See Theorem 3.1.1. It proves that a sub-gaussian random vector is in some sense close in norm to sqrt(n) where n is the number of dimensions. Most of these results are true up to multiplying by some unknown constant.