Corners stick out more in high dimensions

High-dimensional geometry is full of surprises. For example, nearly all the area of a high-dimensional sphere is near the equator, and by symmetry it doesn’t matter which equator you take.

Here’s another surprise: corners stick out more in high dimensions. Hypercubes, for example, become pointier as dimension increases.

How might we quantify this? Think of a pyramid and a flag pole. If you imagine a ball centered at the top of a pyramid, a fair proportion of the volume of the ball contains part of the pyramid. But if you do the same for a flag pole, only a small proportion of the ball contains pole; nearly all the volume of the ball is air.

So one way to quantify how pointy a corner is would be to look at a neighborhood of the corner and measure how much of the neighborhood intersects the solid that the corner is part of. The less volume, the pointier the corner.

Consider a unit square. Put a disk of radius r at a corner, with r < 1. One quarter of that disk will be inside the square. So the proportion of the square near a particular corner is πr²/4, and the proportion of the square near any corner is πr².

Now do the analogous exercise for a unit cube. Look at a ball of radius r < 1 centered at a corner. One eighth of the volume of that ball contains part of the cube. The proportion of cube’s volume located within a distance r of a particular corner is πr³/6, and the proportion located within a distance r of any corner is 4πr³/3.

The corner of a cube sticks out a little more than the corner of a square. 79% of a square is within a distance 0.5 of a corner, while the proportion is 52% for a cube. In that sense, the corners of a cube stick out a little more than the corners of a square.

Now let’s look at a hypercube of dimension n. Let V be the volume of an n-dimensional ball of radius r < 1. The proportion of the hypercube’s volume located within a distance r of a particular corner is V / 2n and the proportion located with a distance r of any corner is simply V.

The equation for the volume V is

V = \frac{\pi^{\frac{n}{2}} r^n}{\Gamma\left(\frac{n}{2} + 1\right)}

If we fix r and let n vary, this function decreases rapidly as n increases.

Saying that corners stick out more in high dimensions is a corollary of the more widely known fact that a ball in a box takes up less and less volume as the dimension of the ball and the box increase.

Let’s set r = 1/2 and plot how the volume of a ball varies with dimension n.

Volume of a ball of radius 1/2 in dimension n

You could think of this as the volume of a ball sitting inside a unit hypercube, or more relevant to the topic of this post, the proportion of the volume of the hypercube located with a distance 1/2 of a corner.

6 thoughts on “Corners stick out more in high dimensions

  1. Johnathan Corgan

    High-dimensional Euclidean spaces are indeed rather unintuitive. A related property to one you describe is that with points uniformly distributed in a unit ball, the ratio of the distance to the farthest neighbor to the nearest neighbor decreases rapidly.

    The practical result of this is that using Euclidean distance as an error measure between points (and therefore also things like mean-squared-error) become useless as a metric.

    In these cases the dot product (which approximates the cosine error) becomes useful, though it’s not strictly a distance metric (fails the inequality triangle.)

    These high dimensional Euclidean spaces come up a lot in machine learning applications and can behave rather surprisingly.

  2. … simplex dihedral angles, on the other hand, get closer to a right angle. You can fit five regular tetrahedra around one edge (which trivializes the first obstruction to a 600-cell); but not five 4-plexes around a triangle.

    @Corgan… I’m fairly certain the same most-likely-ratio will obtain for both sup-norm (mentioned by Grothmann) and l₁ norm; (is this kind of ratio actually a well-behaved statistical thing?) and furthermore, the Euclidean Norms have a huge symmetry group, which should not be ignored lightly…. And… won’t Dot-product exhibit exactly the same problem, just one dimension better?

  3. Maybe I’m weird, but I’ve always thought of higher-dimensional cubes as having “the walls in closer”, that the empty inner “ball” volume is relatively smaller, rather than the corners poking further out.

    Like a sea urchin: The enclosing “ball” is large, but the contained ball is tiny. Which most people would call “poking out”. OK, it is just me.

  4. Prasad Krishnan

    I remembered Shannon’s Channel Coding Theorem for Gaussian channels reading this post. The idea seems almost similar. For a certain fixed noise power (noise being Gaussian, hence the Additive White Gaussian Channel), we approach capacity essentially by sphere packing in large dimensions, i.e., using very long random code.

Comments are closed.