nucleation

QUESTION-251: Do the Johnson–Lindenstrauss threshold for distances and the k log(N/k) threshold for sparse recovery rest on one concentration-of-measure argument, a tail bound for each fixed vector's norm with a union bound over a family, both for sufficiency and for necessity?

2 min read

Properties5
StatusAnswered
Tagsmathematics, learning-theory, neuroscience
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-390 — Any distribution of n × N matrices whose norms concentrate as Johnson–Lindenstrauss proofs require gives the restricted isometry property of order k with probability at least 1 − 2e^{−c₂n} for k ≤ c₁n/log(N/k), by a union bound over (12/δ)^k net points on each of the (eN/k)^k sparse supports; this makes k log(N/k) measurements sufficient for Gaussian, ±1 and sparse three-valued matrices, and does not show they are necessary, THEORY-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, THEORY-395 — For ε between about lg^0.5001 n/√min{n, d} and 1, some n-point set in ℝ^d needs Ω(ε⁻² lg(ε²n)) dimensions under any map, linear or not, that keeps its pairwise squared distances within 1 ± ε, so a random projection with a union bound is optimal up to a constant for the worst set; nearly orthogonal sets can need fewer, and the bound says nothing about typical data, THEORY-397 — A random linear map into k ≥ 4(ε²/2 − ε³/3)⁻¹ ln n dimensions keeps every pairwise squared distance of a fixed set of n points in ℓ₂ within 1 ± ε, because each difference vector's squared length concentrates with tails exp(−(k/2)(ε²/2 − ε³/3)) and a union bound over the pairs costs only ln n; the proofs cover a random subspace, Gaussian entries and independent zero-mean ±1 or √3·{+1, 0, −1} entries, and no matrix with nonnegative entries, THEORY-399 — Storing every inner product of n points of the unit ball of R^k to additive error ε takes Θ(n log n/ε²) bits once k ≥ log n/ε² and Θ(nk log(2 + log n/(ε²k))) below, for 1/n^0.49 ≤ ε ≤ 0.1, and comparing these counts across dimensions shows that some n such points cannot be mapped into fewer than Ω(min{k, log(2 + ε²n)/ε²}) dimensions with additive error ε for every ε ≥ 2/√n; this is a worst-case lower bound with unstated constants, the small-ε bit count is open for k above that dimension, and no one-family embedding that small is proved

Graph View

Answer

For sufficiency, yes. For necessity, no. This is the part of QUESTION-120 that its readings on the first two uses settle, split off on 2026-10-21 (ADR-049).

  • Sufficiency for distances. THEORY-397 (Active). A random linear map into k ≥ 4(ε²/2 − ε³/3)⁻¹ ln n dimensions keeps every pairwise squared distance within 1 ± ε. Each difference vector’s squared length concentrates, and a union bound over the pairs costs ln n. The proofs cover a random subspace, Gaussian entries and zero-mean ±1 or √3·{+1, 0, −1} entries.
  • Sufficiency for sparse recovery. THEORY-390 (Active). The only assumption is the same per-vector tail. A union bound over (12/δ)^k net points on each of the (eN/k)^k supports, and a step from the net to the whole support, give the restricted isometry property for k ≤ c₁n/log(N/k). Any distribution that yields JL embeddings yields RIP matrices.
  • Necessity for distances. THEORY-395 (Active) shows that some n-point set needs Ω(ε⁻² lg(ε²n)) dimensions under any map, by an encoding argument that counts the supports of k-sparse vectors. THEORY-399 (Active) carries the bound to every ε ≥ 2/√n by counting the bits of a distance sketch. Neither is a tail bound on a random map, and neither could be: they bound every map.
  • Necessity for sparse recovery. THEORY-390 records that the paper takes it from Garnaev–Gluskin’s Gelfand widths of the ℓ₁ ball, which is geometry, not concentration. THEORY-391 (Active) gives the sharp location of ℓ₁ recovery as a limit from counting faces of projected polytopes. A union bound gives only its order.

So the two sufficiency proofs are one argument over two families. Both thresholds are the log of the family’s size over a squared tolerance, and recovery’s family adds a k log(12/δ) term. The necessity proofs are different arguments from that one and from each other. THEORY-395’s count ends at m = Ω(k lg(d/k)), the form of the recovery bound, but that is a reader’s observation in NOTE-925, not a shared proof.

What it leaves to QUESTION-120

The answer covers distances and sparse recovery for random matrices. Whether the superposition toy model is limited by recovery or by incoherence, and whether its phase changes are the Donoho–Tanner transition, stay with the parent. So do random features, whose threshold counts features against samples, and expand-and-threshold maps, which go up in dimension. Whether log(2 + ε²n)/ε² dimensions suffice for one set, as THEORY-393 shows for two, is also open.

Backlinks