information
How few bits for a good-enough picture
It is the era when images must fit down thin pipes and onto small disks, and lossless compression is not nearly enough. Accept that some fidelity will be thrown away and ask the sharp question: for a given tolerable distortion, what is the absolute minimum number of bits required to represent the signal — and how do you get near it? Derive the rate-distortion tradeoff and build a coder that spends bits where the eye notices and starves the parts it does not. Get it wrong and you either bloat every photograph with detail no one sees, or crush it into visible garbage — lossy compression lives on this curve, and every image and video standard answers it.
Who this problem belongs to
The two figures whose methods fit it best, out of 38 in contention.
This problem is stated in Shannon's own mathematical language: his 1959 paper 'Coding Theorems for a Discrete Source with a Fidelity Criterion' founded rate-distortion theory outright, formally defining the rate-distortion function as the minimum bit rate achievable for a given tolerable average distortion, exactly the sharp question this problem poses. His earlier 1948 information theory established entropy and channel capacity, the lossless half of the picture, and his 1959 extension supplies the lossy half directly. He did not personally build the JPEG or video coding standards that operationalize this theory decades later, but the entire mathematical framework — the tradeoff curve, its existence, and its characterization — is his own invention, making him the deepest possible fit.
Daubechies's construction of compactly supported orthonormal wavelet bases in the mid-1980s became the mathematical foundation of the JPEG2000 image compression standard, directly operationalizing rate-distortion theory's principle of spending bits where perceptual detail matters and discarding what contributes least. Her rigorous work on wavelets that concentrate a signal's energy into few significant coefficients is precisely the mathematical machinery lossy image compression exploits to approach the rate-distortion bound in practice. Working from the 1980s into the 2000s, as compression standards were actively being redesigned around wavelet transforms, Daubechies did not found rate-distortion theory itself, but her mathematics is directly embedded in the real engineering answer to exactly this problem. Her mathematics is directly embedded in the real modern engineering answer to exactly this problem.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
38 figures are scored on this problem. Draw it in a battle to see where you land.