nucleation

QUESTION-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?

1 min read

Properties5
StatusOpen
Tagsmathematics, mathematical-statistics
Lineformal-apparatus
RefinesQUESTION-120 — Beyond distances and sparse recovery, whose thresholds share a sufficiency proof and not a necessity proof, when the record meets a random linear map that keeps what a later stage needs, in random features for kernels, the superposition toy model's bound and phase changes, and the expand-and-threshold codes of sparse distributed memory and the fly, is it one concentration-of-measure fact applied to different families, and does each threshold count the same thing?
Answered byTHEORY-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

Graph View

Why it is a question

THEORY-391 now states only what was observed, at three problem sizes, with the exponent N^(−1/2) fitted on the same data. Random signs fit the model out of sample, but that is one ensemble at the same sizes. The authors say the result “goes far beyond current theory”, and the universality class is not delineated. The Gaussian curve itself comes from the authors’ earlier face-counting theorems, which the record does not hold.

What would answer it

Either of these would answer it yes:

  • A proof, for some non-Gaussian ensemble in the paper’s class such as random signs, that the ℓ₁ recovery transition converges to the Gaussian ρ(δ; C) as N → ∞.
  • Simulations at problem sizes an order of magnitude beyond N = 1600, in which the gap to the Gaussian curve keeps shrinking as N^(−1/2) for an ensemble not used to choose that exponent.

An ensemble whose gap stops shrinking would answer it no. More simulations at the same sizes do not settle it.

Backlinks