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 3 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 Where a jump puts the error of evenly spread points. Three unit squares with 16, 64, 256 scrambled Sobol' points, one per box, and the line y = 0.15 + 0.7x crossing 6, 12, 26 boxes.

What a jump costs evenly spread points

Scrambled Sobol' points integrate a smooth function with an error that falls like N to the power −3/2. Put a jump in the integrand along a tilted line and the exponent halves, to −3/4, because about √N of the N boxes the points fill are cut by the jump and each of those is left to chance. A jump along an axis costs almost nothing, the cost grows with the length of the jump and the dimension, and integrating across the jump before sampling gives the whole rate back.

probability · Monte Carlo

Named alongside it

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

Convergence rateCentral limit theoremConcentration of measureDimensionDiscrepancyEstimator biasIntegralIsoperimetric inequalityLaw of large numbersLipschitz functionMonte CarloNormal distribution

All concepts