David Donoho

Life and career

David Donoho's academic pedigree is almost comically well chosen for what he went on to do. He took his undergraduate degree at Princeton in 1978, writing a thesis under John Tukey — the man who coined "bit," co-invented the FFT, built exploratory data analysis, and had been arguing since 1962 that statistics ought to reorganize itself around *data analysis*. He then went to Harvard for a PhD, completed in 1983 under Peter Huber, the founder of modern robust statistics and the person most responsible for the idea that an estimator should be evaluated by its worst-case behavior over a neighborhood of models rather than its performance under an assumed one. Tukey's data-first pragmatism and Huber's minimax rigor are the two strands that run through everything Donoho has done since.

He began his faculty career at UC Berkeley in 1984 and moved to Stanford in 1990, where he has remained, now as the Anne T. and Robert M. Bass Professor. He received a MacArthur Fellowship in 1991, was elected to the National Academy of Sciences, and has received the Shaw Prize in Mathematical Sciences and the Carl Friedrich Gauss Prize of the International Mathematical Union — the latter awarded specifically for mathematical work with outstanding applications outside mathematics, which is an accurate summary of his career.

The intellectual arc has a clear logic. In the late 1980s and 1990s he worked on wavelets and nonparametric estimation, establishing that thresholding coefficients in a well-chosen basis is not merely a good heuristic but very nearly optimal in a minimax sense. In the late 1990s and 2000s he pushed the underlying insight — that real signals are *sparse* in some representation, and that sparsity is information the classical parameter count throws away — into the theory of underdetermined linear systems, arriving at compressed sensing. Along the way he developed, with Jared Tanner, a startlingly precise account of *when* sparse recovery works: not a rate, but a sharp phase transition in the plane of undersampling ratio against sparsity, above which recovery succeeds with overwhelming probability and below which it fails.

Donoho is also one of academic statistics' most persistent institutional critics, and unusually, a constructive one. He was an early and forceful advocate for reproducible computational research, releasing the WaveLab and SparseLab toolboxes precisely so that every figure in his papers could be regenerated by a reader — advancing the argument, associated with the geophysicist Jon Claerbout and carried into statistics by Donoho and his collaborators, that a paper about computational science is advertising for the scholarship rather than the scholarship itself. His 2015 essay "50 Years of Data Science," written for Tukey's anniversary, is the most careful account anyone has given of what "data science" is, what statistics contributed to it, what statistics failed to do, and what a genuine science of data analysis would have to look like. It named the discipline's identity crisis before it was fashionable to have one.

Key contributions

**Wavelet shrinkage denoising.** With Iain Johnstone, in a series of papers in the mid-1990s, Donoho gave the canonical solution to nonparametric denoising: transform the noisy signal into a wavelet basis, apply a threshold to the coefficients, transform back. The **soft threshold** η_λ(y) = sign(y)(|y| − λ)₊ is the one to remember; it is also the proximal operator of the L1 norm, which is why the same operation reappears everywhere in sparse optimization. Two choices of λ matter. **VisuShrink** uses the universal threshold σ√(2 log n), chosen so that pure noise coefficients are, with high probability, all killed. **SureShrink** chooses λ level-by-level by minimizing Stein's unbiased risk estimate, adapting to the actual sparsity of each resolution level.

The theoretical result is what makes this more than a recipe. Donoho and Johnstone proved that wavelet thresholding is **near-minimax over a wide range of smoothness classes simultaneously** — within a logarithmic factor of the best achievable risk, without knowing which class the truth belongs to. This is spatial adaptivity: the estimator smooths heavily where the function is smooth and preserves sharp features where it is not, which no linear smoother with a single bandwidth can do. Every graduate student who has ever chosen a bandwidth and watched it blur an edge should understand exactly what problem this solves.

**Minimax theory over sparse classes.** Underneath the wavelet work is a general decision-theoretic program: characterize the minimax risk of estimating a vector known only to be sparse, and show which estimators attain it. The recurring answer is that thresholding is asymptotically optimal, and that the minimax risk scales like 2 log(n) times the sparsity — the logarithmic factor being the unavoidable price of not knowing *which* coefficients are the large ones.

**Uncertainty principles and basis pursuit.** With Philip Stark (1989) and later with Xiaoming Huo, Donoho developed discrete uncertainty principles: a signal cannot be simultaneously concentrated in two mutually incoherent bases. This converts into a uniqueness theorem — if a representation in an overcomplete dictionary is sparse enough relative to the dictionary's mutual coherence, it is the *only* such sparse representation. Basis pursuit (Chen, Donoho, and Saunders, 1998) then shows that the intractable L0 problem can be replaced by L1 minimization, a linear program, and still find that unique sparse solution.

**Compressed sensing.** The 2006 paper crystallized the program, concurrently with and complementary to the work of Candès, Romberg, and Tao. The claim: if a signal is k-sparse in some basis, it can be recovered exactly from roughly O(k log(n/k)) random linear measurements, far below the Nyquist count the ambient dimension would demand, by solving an L1 minimization. The consequences reached MRI acquisition, radar, and single-pixel imaging. With Tanner he then computed the **phase transition** precisely, using the geometry of random polytope projections and neighborliness — a sharp curve, verified numerically to remarkable accuracy, separating the recoverable regime from the impossible one.

**Optimal shrinkage for matrices.** With Matan Gavish, the exact optimal hard threshold for singular values when denoising a low-rank matrix in white noise — the constant 4/√3 for square matrices — derived from random matrix theory. This is the principled replacement for eyeballing a scree plot.

**Robustness.** With Huber, foundational work formalizing the **breakdown point** — the smallest fraction of contamination that can drive an estimator arbitrarily far from the truth — and the Stahel–Donoho estimator of multivariate location and scatter, based on maximal univariate outlyingness over projections.

In battle

Donoho's computed profile is a strong specialist's, with the specialty being high-dimensional structure: mean 37.0 across 100 problems, **ten dominant scores**, and thirty-three problems at 20 or below. His high-dimensional category average of **86.4 across eight problems** is among the highest concentrated category scores in the game.

His peak is **P094 — Reconstruct from too few measurements** (95): compressed sensing, where the judge calls him a genuine co-author of the theorem being asked for, and notes that the problem's premise — sparsity is information the classical count ignores — is essentially his framing verbatim. **P018 — p = 20,000, n = 200** (94) is the same idea in the genomics regime; he sits just behind Tibshirani's 98 there, appropriately, since the lasso is the tool and the minimax theory of sparse estimation is the justification. **P095 — The wavelet decomposition** (90) puts him behind Daubechies's 98 — she constructed the wavelets, he proved what you should do with the coefficients. **P288 — Let the images choose the basis** (93) rewards his work on overcomplete dictionaries and on geometric multiscale representations such as curvelets and ridgelets. **P282 — The eigenvalues are lying** (93) is the Gavish–Donoho singular-value shrinkage result exactly. **P285 — Test the many with the blood of few** (92) is pooled testing, which is combinatorial group testing and is also, viewed correctly, sparse recovery from few measurements. **P124 — Twenty thousand tests at once** (88) is large-scale multiple testing, and **P182 — The corner that sparsity loves** (88) is the L1 geometry. His optimization average of 66.5 reflects that his sparse-recovery work is convex programming in substance.

The losses are unusually clarifying, because they are almost all *causal or paradox* problems. He scores 10 on **P214 — The paradox in the admissions data** — the Berkeley Simpson's paradox problem where Bickel scores 98 — and 9 on **P143 — The coefficient that flips sign**. He scores 12 on **P209 — The pump on Broad Street**, John Snow's cholera investigation. His causality average is 24.9. The pattern is worth stating plainly to students: Donoho's toolkit answers "what is the signal, and can I recover it?" with extraordinary precision, and is entirely silent on "why is this association here, and would it survive intervention?" Sparse recovery presumes a linear measurement model that already encodes the structure; a confounder is not a measurement error.

The remaining losses are adversarial or engineering. **P202 — The bluff is the mathematics** (9) is poker and equilibrium computation; the judge allows a loose thematic echo — abstracting an astronomically large game tree resembles compressing a large object — while noting he has not published in game theory. **P208 — The missile and the evader** (10) is pursuit-evasion, **P254 — The wall around the data structure** (10) is software encapsulation, and his systems (12.5) and games (9.5) categories are near the floor.

Draft Donoho for anything where the truth is sparse, the measurements are few, and the question is whether recovery is even possible. He is the roster's best answer to "how much can you get from how little?" — and its worst answer to "why?"