6
$\begingroup$

Suppose we sample a set $S$ of $n$ points from a $d$-dimensional spherical (unit variance) Gaussian with $d \approx 100$. It is known that any point of the sample would be roughly at $\sqrt{d}$ distance away from the center with high probability. Let $c$ denote the center of the Gaussian.

Let us choose any point $p$ from the sample, and let $T$ denote the set of $t$ closest points of $p$ in $S$. We observe that $||c-\text{mean}(T)|| \ll \sqrt{d}$. What would be the reason for mean$(T)$ to be much closer to the center than any random point of the sample? Any help is appreciated.

Assume $n$ to be in millions and $t$ be of the order of hundreds.

$\endgroup$
  • $\begingroup$ (1) Does "whp" mean "with high probability"? (2) "$\ll$" is meaningless and often false. To make it meaningful you need to compare the left hand side to the right hand side relative to $n$ and $t$. $\endgroup$ – whuber Sep 20 '16 at 15:34
  • 1
    $\begingroup$ Edited the question to clarify. For (1), yes. For (2), assume n to be in millions and t to be in hundreds. $\endgroup$ – anup Sep 21 '16 at 4:04
6
$\begingroup$

This is a question about high-dimensional Euclidean geometry, related to the "curse of dimensionality". It comes down to this: almost all the surface area of a sphere in $d$-dimensional Euclidean space $E^d$ is concentrated around its equator. The nearest neighbors of any point will tend to be scattered in random directions around its equator, so their average will be near its center--which is the center of the sphere itself.

The rest of this post explains why this is, provides an estimate for how much the distance shrinks, and presents a simulation (in $100$ dimensions) to support the conclusions.


There's a nice statistical demonstration of this equatorial concentration lemma. Given that the squared radii of the points are concentrated around $d$ (a consequence of their $\chi^2(d)$ distribution), which places them close to a sphere of radius $\sqrt{d}$, we need only consider the angles made between the nearest neighbors with the original point. For each such angle $\theta$, use $(\cos(\theta)+1)/2$ to measure its size. This value decreases from $1$ with close neighbors, through $1/2$ at the equator, down to $0$ for diametrically opposite points. It has a Beta$((d-1)/2,(d-1)/2)$ distribution.

I don't want to presume too much knowledge of Beta distributions, because little is actually needed. Here is an elementary way to reason about this particular distribution. Its mean is $1/2$--on average all the remaining points are halfway between a given point and its opposite--and its variance is $1/(4d)$. Its spread, as measured by the standard deviation, therefore is $1/(2\sqrt{d})$. Chebyshev's Inequality states that for any $k\ge 1$, at most $1/k^2$ of the probability lies beyond $k/(2\sqrt{d})$ of the equator. That's all we need to know.

Fixing the number of points $n$ and the number of nearest neighbors $t$, choose $k$ so large that $t/n$ is substantially greater than $1/k$: a small multiple of $n/t$ will do. As $d$ grows, the value $k/(2\sqrt{d})$ shrinks down to zero. Therefore most of the $t$ nearest neighbors of any chosen point will be close to the equator.

With this geometric result in mind, the answer is now obvious. The nearest neighbors of any given point will be scattered randomly near the equator within limited distances of the equator relative to that point. The cylindrical symmetry of the situation around the point's axis indicates that on average those neighbors will be almost directly beneath the north pole. Thus we expect this average of the neighbors to be much nearer the origin than the original point itself, which is close to $\sqrt{d}$.


That's more or less a heuristic argument but we can obtain quantitative results, too. We may freely rotate the coordinate system so that the original point is "up," because a rotation changes neither the distances nor the probability distribution of the points. The height, in particular, has a standard Normal distribution. The average of the $t$ largest out of $n$ independent heights will be close to the average of their expectations and less than the expected maximum height. An approximation for that expected maximum is $\Phi^{-1}(1-1/(n+1))$ where $\Phi$ is the standard Normal distribution function. At the same time, each coordinate of the average is the average of $t$ standard Normal variables. The first $n-1$ of these coordinates are approximately independent of the last and their averages have Normal distributions with zero mean and variance of $1/t$. The sum of their squares consequently is approximately a multiple of a $\chi^2(d-1)$ distribution, with a mean of $(d-1)/t$. Therefore the squared distance of this average is expected to be near $$h(n,d)=(d-1)/t + \Phi^{-1}(1-1/(n+1))^2$$ and likely a little bit less. This is a reasonable estimate when $t$ is small compared to $n$; it becomes a gross overestimate as $t$ grows.

We may explore this situation via simulation, using (a) the $\chi^2(d)$ distribution of all squared distances as one reference and (b) this estimate $h(n,d)$ as another reference. Here, for instance, is a histogram of the lengths of the mean of $t=9$ nearest neighbors for $n=10^4$ points in $d=100$ dimensions. To standardize the comparison (which helps when varying $d$), all distances have been divided by $\sqrt{d}$, thereby bringing the points close to the unit sphere.

Figure

The blue curve is the standardized $\chi^2(100)$ density. The vertical dashed red line is the (over)estimate of the typical distance between the average of the nine nearest neighbors and the center of the sphere. The histogram displays the simulated data, which are based on $10$ independent sets of points and $50$ randomly selected points out of each of those sets.

That the histogram is situated close to, but a little less than, the vertical red line supports the preceding quantitative analysis. That both are substantially less than $1$ supports the statement in the question itself.

For those who would like to experiment, here is the R code to produce similar situations. Take care when increasing any of the inputs, because the calculations can take a long time.

n <- 1e4    # Number of points
m <- 50     # Subset size
k <- 9      # Number of nearest points
d <- 100    # Dimension
n.sim <- 10 # Number of trials

#set.seed(17)
sim.raw <- replicate(n.sim, {
  x <- matrix(rnorm((n+1)*d), d)
  sapply (sample.int(n+1, m), function(i) {
    distance.2 <- colSums((x - x[, i])^2)
    q <- x[, order(distance.2)[1:k + 1], drop=FALSE]
    q.mean <- rowMeans(q)
    sum(q.mean^2)
  })
})
sim <- sqrt(sim.raw / d)

h <- sqrt((qnorm(1/(n+1))^2 + (d-1)/k)/d) # Overestimate of the mean
hist(sim, xlim=range(c(sim, h, 0, 1 + 2*sqrt(d-1)/d)), freq=FALSE,
     xlab=paste("Length of standardized mean of", k, "nearest neighbors"),
     main=paste("n =", n, "points in d =", d, "dimensions"),
     sub=paste(n.sim, "trials using", m, "points per trial"), cex.sub=0.8)
abline(v=h, col="Red", lty=3, lwd=2)
abline(v=mean(sim), col="Gray", lwd=2)

curve(2 * x * dchisq(x^2*d, df=d) * d, add=TRUE, col="Blue")
$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. May be I am lacking some basics, would you please elaborate (or references) why nearest neighbors will be scattered randomly near the equator. $\endgroup$ – anup Sep 24 '16 at 9:33
  • 1
    $\begingroup$ That's exactly what is demonstrated in the argument leading up to the reference to Chebyshev's inequality. I'll see whether I can clarify that. $\endgroup$ – whuber Sep 24 '16 at 14:42
  • $\begingroup$ Two clarifications: For each angle \theta, why do you say that estimated size to be (cos(\theta)+1)/2. Secondly, why approximation for expected maximum is \phi^(-1)(1-1/(n+1)). Thanks. $\endgroup$ – anup Sep 25 '16 at 12:42
  • 1
    $\begingroup$ $(\cos(\theta)+1)/2 = \sin^2(\pi/2-\theta/2)$ is proportional to the squared angle that $\theta$ makes with the equator. It therefore is an excellent measure of how far from the equator that angle is. A search of our site provides detailed information and derivations concerning your second question: see, for instance, stats.stackexchange.com/questions/9001. $\endgroup$ – whuber Sep 26 '16 at 13:42
  • $\begingroup$ I was playing with these things. Let d=400 and n=1,00,000 points from N(0,I_d). Let p1 be randomly chosen from N(0,I_d) and p2=-p1. Let C1,C2 be two clusters (k-means) with respect to p1 and p2, and c1=mean(C1) and c2=mean(C2). I was trying to apply the above reasoning in this case. But simulation results seem to suggest that points in the clusters would not be independent, and therefore, ||c_1|| or ||c_2|| can not be justified with formula like h(n,d) in above (ignoring the phi^(-1) term). In other words, points in the clusters would be correlated. Yours thoughts please. $\endgroup$ – anup Sep 30 '16 at 7:12
3
$\begingroup$

First of all, a comment on the question: Points in the sample $S$ won't be at $\sqrt{d}$ distance away from the center. Distance squared will follow a $\chi^2$ distribution with $d$ degrees of freedom and therefore with $d$ mean and $2d$ variance. Then, distance will be distributed around $\sqrt{d}$ but there is not a concentration of points in the $\sqrt{d}$ radius shell.

And for the question itself, I don't see how you observe that $||c-\text{mean}(T)|| << \sqrt{d}$, and in fact $||c-\text{mean}(T)||$ depends a lot on how has been $T$ selected. I'll comment two extreme cases:

  • If $T$ is much smaller than $S$: $T$ (the $t$ points closer to $p$) are likely to be very close to $p$ and therefore distribution of $\text{mean}(T)$ will be very close to the distribution of $p$, and $||c-\text{mean}(T)||^2$ will approximately follow a $\chi^2$ distribution with $d$ degrees of freedom and therefore with $d$ mean and $2d$ variance, just like distance of $c$ to $p$.
  • If $T$ is nearly as large than $S$: Then $T$ is approximately a random sample from the d-dimensional spherical (unit variance) Gaussian distribution. When finding $\text{mean}(T)$, for each dimension we are averaging $t$ points from a normal distribution, and in the whole we get a d-dimensional spherical Gaussian distribution with $1/t$ variance, and $t·||c-\text{mean}(T)||^2$ will follow a $\chi^2$ distribution with $d$ degrees of freedom. Mean of $||c-\text{mean}(T)||^2$ will be $d/t$ and variance $2d/t$. Then $||c-\text{mean}(T)||$ will be distributed around $\sqrt{d/t}$, and for larger $t$ it will be much smaller than $\sqrt{d}$.
$\endgroup$
  • $\begingroup$ You are right about the distance of any random point of the sample from the center. Of the two cases you have mentioned above, I am looking for Case 1, say n=|S| in millions and t in hundreds. Yes, it is not clear why mean(T) should be much closer to the center c, but that is what we observed. $\endgroup$ – anup Sep 21 '16 at 4:09
  • $\begingroup$ What do yo mean by "we observed"? Have you run a simulation? Have you done some maths? Without more details we can't give hints about why you observed that. $\endgroup$ – Pere Sep 21 '16 at 8:52
  • $\begingroup$ By the way: In more than one dimension, mean of distances of points in a sample should be larger than distance to mean of points, as shown by extreme cases, but if all points in the sample are close this effect should be small. $\endgroup$ – Pere Sep 21 '16 at 9:04
  • $\begingroup$ Yes, we ran simulations where we observed this event. $\endgroup$ – anup Sep 21 '16 at 15:40
  • $\begingroup$ Since the closest t points to p would be correlated, it is not clear how to compute the distribution of average of these points $\endgroup$ – anup Sep 23 '16 at 5:28

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.