Matpic
mathematics, in pictures
Concept

Curse of dimensionality

The collective name for the ways space behaves against intuition when it has many dimensions, making grids, searches and samples exponentially costly. Nearly all of a high-dimensional ball's volume lies near its surface and near every equator, so random points are far from the centre and from each other.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

How fast each way of averaging closes in, as the dimension grows. Relative error against the number of points, both on logarithmic scales, for a regular grid in 1, 4, 8 dimensions and for random points in 8; the grid's lines steepen or flatten with the dimension and the random one does not move from a slope of a half.

The error that does not care how many dimensions

A grid gets rapidly better in one dimension and hopelessly worse in twenty. Random points get better at the same slow rate whatever the dimension, which is why a method that is bad everywhere ends up being the only one that works.

probability · Monte Carlo How much of a sphere lies near its equator. Curves of the share of the sphere within ε of the equator against ε, for spheres in 3, 10, 100, 1000 dimensions: a straight line in three dimensions, a near step in a thousand.

A sphere that is nearly all equator

On an ordinary globe, the band within a tenth of the radius of the equator holds a tenth of the surface. On a sphere in a thousand dimensions the same band holds 99.85% of it, and the band of a fifth holds all but about two parts in ten billion. Almost every point of a high-dimensional sphere is near every equator at once — and so any function that cannot change quickly is, over almost all of the sphere, almost constant.

probability · Concentration

Named alongside it

The objects these essays reach for when they reach for this one.

Central limit theoremConcentration of measureConvergence rateDimensionEstimator biasIntegralIsoperimetric inequalityLaw of large numbersLipschitz functionMonte CarloNormal distributionOrthogonality

All concepts