This is from Exercise 2.4 (Page 39) of Elements of Statistical Learning:

The edge effect problem discussed on page 23 is not peculiar to uniform sampling from bounded domains. Consider inputs drawn from a spherical multinormal distribution $X ∼ N(0,\mathbf{I_p})$. The squared distance from any sample point to the origin has a $\chi_p^2$ distribution with mean $p$.

Consider a prediction point $x_0$ drawn from this distribution, and let $a = \frac{x_0}{\|x_0\|}$ be an associated unit vector. Let $z_i = a^Tx_i$ be the projection of each of the training points on this direction.

Show that the $z_i$ are distributed $N(0,1)$ with expected squared distance from the origin 1, while the target point has expected squared distance $p$ from the origin.

Hence for $p = 10$, a randomly drawn test point is about 3.1 standard deviations from the origin, while all the training points are on average one standard deviation along direction $a$. So most prediction points see themselves as lying on the edge of the training set.

I understand all the calculations necessary here:

  • a $\chi_p^2$ distribution is by definition the sum of $k$ independent standard normals and has mean $k$, and the squared part takes care of the root in the definition of Euclidean distance
  • any linear combination of normals is normal itself, and takes variance 1 because the magnitude of the projection $\|a^T\|$ is 1
  • the expectation of the squared distance from origin of this single standard normal is 1, compared to 10 (or expected distance from origin of $\sqrt{10}$) when considering again a sample from a 10-dimensional space pulled from independent standard normals.

What I don't get is how this is an indication of the curse of dimensionality or data points drifting toward the edge and away from other points as the number of dimensions increase. Why are we taking the unit vector projection of one point onto all the training points?


2 Answers 2


The relevant quote from page 23 of Elements of Statistics: "Hence most data points are closer to the boundary of the sample space than to any other data point. The reason that this presents a problem is that prediction is much more difficult near the edges of the training sample. One must extrapolate from neighboring sample points rather than interpolate between them."

If $x_0$ is > 3 standard deviations from the origin, that means that on average well under 1% of sample points will be further from the origin in the direction of $x_0$. So the sample size would have to be very large to avoid the problem of $x_0$ being at the edge of the sample.


For the question "Why we are taking the unit vector projection of one point onto all the training points", it is easy to figure it out because when you make a prediction, the neighbors are chosen from training data which are close to the prediction point $x_0$. And the unit vector projection is the distance of training point $x_i$ to the prediction point $x_0$. So you can see that the training data in that direction have a much closer expected squared distance than the prediction point. So most prediction points see themselves as lying on the edge.


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.