# High dimensional space is dense or sparse?

I read some blog articles recently. One mentions that you could not imagine high dimensional space as 2d or 3d as distance between any 2 points in high dimensional space tends to be similar, which means 'dense'. However in the t-SNE paper, it says high dimensional space tends to be sparse such that you have to employ special dimensionality reduction techniques to visualize in 2d or 3d space in meaningful way. So how to reconciliate these 2 different views?

• please add a link to this blog article – Martin Thoma Oct 19 '16 at 14:24
• @MartinThoma Yes exactly:) I forget where is the blog article. I'd update if I recall it later. BTW, you seem having a good blog site. But your profile link is missing. – Michael SM Oct 19 '16 at 15:16
• @MartinThoma Thank you for adding t-SNE paper link. – Michael SM Oct 20 '16 at 5:13
• – Emre Oct 20 '16 at 6:40

Data in a high dimensional space tends to be sparser than in lower dimensions. There are various ways to quantify this, but one way of thinking that may help your intuition is to start by imagining points spread uniformly at random in a three dimensional box. Now flatten the box into a square, pushing two opposite sides together so all the points lie on a single plane. Do you see that the average distance between a point and its nearest neighbor is now smaller? Now flatten the square into a line segment. Do you see that the average distance between a point and its neighbors is now smaller still?

There is no conflict between this and saying that the average distance between any 2 points in the high dimensional space tends to be similar. The latter statement doesn't imply density. The real number line is dense (it has no gaps), and yet the distance between points ranges from 0 to infinity. The point is that the higher the dimension of your space, the more likely the points are to lie near the edges of the space rather than the center.

Again, consider the dimensions we can actually see. Consider a circle with radius=1, inscribed in a square with sides of length=2. The circle occupies $\pi / 4$ of the square's area, about 78.5%. Now consider a sphere of radius=1 inscribed in a cube with sides of length=2. The sphere occupies $\pi / 6$ of the cube's volume, about 52.4%. As you see in this example, the odds of a randomly placed point lying close to the center (with close to the center in this case meaning within the circle or the sphere) is lower as the dimension increases. Points are more likely to be in the corners. This is why in high dimensions the distance between the points tends to be similar - because randomly placed points tend to be close to the edges of the region.

• Another example I like: take 6 points evenly distributed on a circumference and they will be 60º apart; 6 points evenly distributed in the surface of a sphere will be 90º apart. – Pere Oct 18 '16 at 18:34
• @Pere That's a good one, and a good complement to my answer, since it makes clear that the increasing sparseness isn't something unique to square boxes. – Tim Goodman Oct 18 '16 at 18:46

I would like to elaborate a bit on the fact that data in high dimensional spaces is sparser.

Usually, we think of euclidean spaces. This means if we have points $p_1, p_2 \in \mathbb{R}^n$ we say their distance is

$$d(p_1, p_2) = \sqrt{\sum_{i=1}^n {\left (p_1^{(i)} - p_2^{(i)} \right )}^2}$$

So we take the square root of the sum of the component-wise squared difference.

Now think of two points in a unit hypercube in $\mathbb{R}^n$ (hence $[0, 1]^n$). The maximum distance two points can have in this hypercube is when they are on the diagonal. Hence the distance is $\sqrt{n}$, meaning the higher the dimension is, the farer away can points be in the unit hypercube.