What is curse of dimensionality?

Definition

The number of possible combinations grows rapidly as dimensions are added. A fixed dataset can then cover little of the space, making patterns harder to estimate.

Real observations may have related or redundant variables. Representing the structure with fewer useful dimensions can make some tasks more tractable.

ELI5

For example, sorting one measurement into ten groups gives ten bins. Sorting five measurements that way yields one hundred thousand combinations.

The same examples cover a much smaller fraction of the larger collection of bins, so useful comparisons can become rare.

Does it affect every dataset equally?

It depends on the method and the structure in the data. Measurements can contain redundant information.

Why can learned representations help?

They can emphasize useful structure and reduce the number of dimensions a later step has to consider.

  1. Portraits of Tim Scarfe and Matthieu Wyart beside the words Predict Latents
Definition card for curse of dimensionality: What is curse of dimensionality?

The curse of dimensionality describes problems that become harder as the number of independent variables increases.