David L. Donoho and Jared Tanner (2009), “Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing”, Philosophical Transactions of the Royal Society A 367(1906): 4273–4293 — ARXIV-0906.2530, doi:10.1098/rsta.2009.0152
Key takeaways
From the reading, NOTE-933.
- The Gaussian theorem, restated (Theorem 2.1). For A n × N with iid N(0, 1) entries, n = δN, k = ρn and N → ∞, the expected fraction of k-faces of the simplex T or cross-polytope C that survive projection by A tends to 1 for ρ < ρ(δ; Q) and to 0 for ρ > ρ(δ; Q). By Lemmas 2.1–2.2 that fraction is the fraction of k-sparse vectors recovered by (LP) (nonnegative) or (P1) (ℓ1 minimization). It was proved in the authors’ earlier papers; this one gives no formula for ρ(δ; Q). The figures print ρ(δ; C) values, e.g. 0.189 at δ = 0.1, 0.3848 at 0.5, 0.6773 at 0.9.
- Two curves, not one. ρ(δ; T) > ρ(δ; C) for δ ∈ (0, 1). The paper checks both, with 8 non-Gaussian ensembles each: Bernoulli, partial DCT, three ternary densities, partial Hadamard, Expander and Rademacher.
- Strict universality rejected, weak universality kept. Over 16,984 settings and 2,948,000 linear programs at N = 200, 400 and 1600, the two-sample Z-scores against the Gaussian are mostly within ±2, but their means trend significantly with δ. The trend terms decay as N^(-1/2) (γ = 1/2 gives the best R², 0.976 and 0.982, Table 8), and terms that do not decay add nothing (F = 0.7467, p = 0.7475, §5.5).
- Finite-N width. For the Gaussian, success falls as Φ̄((ρ − ρ(δ; Q))/w) with √N · w between 0.62 and 0.73 (Table 5).
- Sparse matrices are late joiners. Ternary (1/10), Expander and Hadamard have their 50% point about one transition width below the curve at N = 200 to 256, because sparse matrices at small n have sparse null vectors (an all-zero column, null vectors with 6 nonzeros). At N = 1600 the effect is gone (§5.7).
- Decoder-specific. Other recovery algorithms show other transitions (§3.7). Cyclic polytopes do better than random matrices, and the all-ones matrix is a trivial counterexample.
- Status of the claim. Observed, not proved. The authors pose the open problem of characterizing the ensembles that share the Gaussian transition, and they note that Adamczak et al. (2009) proved a success region for some ensembles without matching the Gaussian one.
Standing in the record
Filed on 2026-10-14 for QUESTION-120 and read the same day in NOTE-933. Toy Models of Superposition asks whether its phase changes relate to the Donoho–Tanner transition (NOTE-278), and the record could not follow the question without the transition itself. The question says Donoho and Tanner “observe that the sparse-recovery transition does not depend on the ensemble”. The reading corrects that: they observe it for eight ensembles and only as N grows. At finite N the transition does depend on the ensemble, and for sparse matrices by a full transition width at small N.
For the question the reading gives three things. The Donoho–Tanner
threshold is an exact limiting location from face counting, not a
log-family-size bound from a union bound, so it does not fit the
question’s proposed shape. A comparison with the toy model must use
δ = m/n and ρ = k/m and reckon with the paper’s statement that the curve
belongs to the ℓ1 decoder. And the sparse ensembles closest to the fly’s
and SDM’s maps were the ones that failed at small size. The
mathematical-statistics tag is for its reading of the transition as a
hard limit on what can be inferred from undersampled data, which the
abstract states.
Filed as THEORY-391, Proposed, because the universality it reports is observed at three problem sizes.