What is the "Curse of Dimensionality?"

Curse of Dimensionality

The difficulty of searching through a solution space becomes much harder as you have more features (dimensions). Consider the analogy of looking for a penny in a line vs. a field vs. a building. The more dimensions you have, the higher volume of data you’ll need.

High dimensionality makes clustering hard, because having lots of dimensions means that everything is “far away” from each other. It’s hard to know what true distance means when you have so many dimensions. That’s why it’s often helpful to perform PCA to reduce dimensionality before clustering.

High dimensionality is also a curse when one is trying to do rejection sampling. With a higher dimension probability distribution, it becomes increasingly harder to find an appropriate enveloping distribution since the acceptance probability will keep shrinking with dimensionality.