Explanation for this event on a high-dimensional dataset

Question

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.

Answer 1

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.

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")

Answer 2

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}$.