The Curse of Dimensionality and Density in the Structure of Nature

The interactive application below was inspired by Richard Hamming's The Art of Doing Science and Engineering. The iconic image below at left is 976 pixels wide by 1200 pixels high in the original file. Since the image is in greyscale, the colour of each pixel is represented by an integer value in the range [0, 255].

Thinking more generally about images as systems, there are (976x1200)²⁵⁶ possible configurations (states). Each pixel can take one of 256 values, and there are 976 x 1200 = 1,171,200 pixels. The number of possible unique images is then 256^1,171,200, or roughly 10^3,529,089. In other words, this image is unimaginably unique.

In the interactive visualization below, the original source image (top left) is compared with a downsampled version (top right), and a random image from the same state space (bottom left). Change the dimensions and colour depth to see how quickly the number of possible images grows.

It's not really possible to imagine such large numbers, but as a basis of comparison, the cosmological estimate of the number of atoms in the universe is about 10⁸⁰. The set of all 976 x 1200 images that humans can recognize is effectively zero against such an unimaginable proportion of possibilities. If every human that ever lived spent their entire lifetime looking at 976 x 1200 images with randomly assigned pixel values, virtually all images drawn would be like static on an old CRT TV.

So what is it about natural systems that makes pattern recognition not just possible, but common? For starters, we don't need a perfect match to recognize a pattern. The human visual system is remarkably robust to noise and distortion, and can recognize patterns even when they are partially obscured or altered. Natural systems tend to exhibit certain regularities and structures that can be exploited for recognition, and this significantly reduces the effective complexity of the recognition task.

Reference

1. Hamming, Richard W. The art of doing science and engineering: Learning to learn. Stripe Press, 2020.