nucleation

THEORY-812: As dimension grows with the undersampling and sparsity ratios fixed, the ℓ₁ phase transition for recovering sparse vectors from random measurements sits at the same curve for a broad class of random-matrix ensembles, those with a kind of orthogonality or weak independence, as for Gaussian matrices, while differing at finite size

2 min read

Properties5
StatusProposed
Tagsmathematics, mathematical-statistics
SourceLIT-1160 — Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
ExtendsTHEORY-391 — Recovery of a k-sparse vector by ℓ₁ minimization from n random measurements in dimension N switches, as N grows with δ = n/N and ρ = k/n fixed, from near-certain success to near-certain failure across a curve ρ(δ) that, for Gaussian matrices, the authors' earlier face-counting theorems fix; in 2,948,000 optimizations at N = 200, 400 and 1600, eight non-Gaussian ensembles approached that curve in a way consistent with gaps shrinking as N^(−1/2), an exponent fitted on the same data, while at finite N the location depended on the ensemble
AnswersQUESTION-168 — Does the ℓ₁ recovery transition of some non-Gaussian measurement ensemble provably converge to the Gaussian curve ρ(δ) as N → ∞, or do simulations an order of magnitude beyond N = 1600 keep the gap shrinking as N^(−1/2) for an ensemble not used to choose that exponent?

Graph View

Source

Donoho and Tanner (2009), LIT-1160, read in NOTE-933: Findings 1 and 3 and claim C2 (“weak universality”, moderate), with the class left undelineated (§3.7: ensembles with “a certain air of ‘orthogonality’ or ‘weak independence’”). The analogy to a new limit theorem (C7) is weak and is not part of this thesis.

What is asserted, and by whom

The thesis is weak universality: for the two decoders studied, the large-N location of the ℓ₁ transition does not depend on the measurement ensemble within a broad class that includes the eight non-Gaussian ensembles tried. Strict, finite-N universality is not claimed; the authors reject it.

What the record holds toward it

  • THEORY-391 (Active): the eight ensembles approach the Gaussian curve at N = 200, 400 and 1600, consistent with gaps shrinking as N^(−1/2), an exponent fitted on the same data.
  • The Gaussian curve itself is a theorem, by the authors’ earlier face-counting results.

What would confirm or reject it

A proof of convergence to the Gaussian curve for some non-Gaussian ensemble in the class, or simulations an order of magnitude larger with the gap still shrinking for an ensemble not used to fit the exponent, would confirm it. An ensemble of the class whose large-N transition sits elsewhere would reject it. QUESTION-168 asks this as a question; this entry is the answer Donoho and Tanner propose.

Backlinks