high-dim
Reconstruct from too few measurements
It is 2004, and the Nyquist–Shannon doctrine has hardened into common sense: to recover a signal you must sample at twice its bandwidth, full stop. But the signals that matter — medical images, spectra, photographs — are sparse in the right basis, and sparsity is information the classical count ignores. Recover a sparse signal from far fewer linear measurements than dimensions, with a proof, not a prayer: conditions on the measurement matrix under which convex relaxation provably finds the exact sparse solution, with high probability, from random measurements. The application waiting on the theorem is not abstract: MRI scan time scales with measurement count, and a child who must hold still — or be anesthetized — is the unit in which this theorem's success is measured.
Who this problem belongs to
The two figures whose methods fit it best, out of 57 in contention.
Candes is, with Tao and Donoho, a co-founder of compressed sensing, and this problem restates his and Tao's 2005-2006 results almost exactly: precise conditions on measurement matrices — the restricted isometry property — under which L1 convex relaxation provably recovers a sparse signal exactly from random linear measurements with high probability, with medical imaging as a central motivating application. His subsequent extensions to matrix completion and continued work on provable recovery guarantees make him arguably the single most directly matched carrier for this problem in the entire pool; this is not analogous to his career, it is his career, restated as a problem prompt.
Tao is, with Candes, the co-author of the compressed-sensing breakthrough this problem restates directly: the precise conditions on random measurement matrices under which L1 convex relaxation provably recovers a sparse signal exactly with high probability, published in their landmark mid-2000s papers. His mathematical range across harmonic analysis, combinatorics, and analysis made the restricted-isometry-property proof technique possible, and his continued work on related recovery and estimation problems shows sustained engagement with exactly this territory. He is one of the two or three strongest possible carriers in this entire pool; this problem is a direct restatement of his own published result.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
57 figures are scored on this problem. Draw it in a battle to see where you land.