Richard Baraniuk, Mark Davenport, Ronald DeVore and Michael Wakin (2008), “A Simple Proof of the Restricted Isometry Property for Random Matrices”, Constructive Approximation 28(3): 253–263 — doi:10.1007/s00365-007-9003-x
Key takeaways
From the reading, NOTE-931.
- The one assumption (4.3). For every fixed x, Pr(|‖Φx‖²_{ℓ₂ⁿ} − ‖x‖²_{ℓ₂ᴺ}| ≥ ε‖x‖²_{ℓ₂ᴺ}) ≤ 2e^{−n c₀(ε)}, 0 < ε < 1. Φ is n × N: n measurements, ambient dimension N.
- Ensembles (§4). Gaussian N(0, 1/n), ±1/√n, and the sparse ±√(3/n) with probability 1/6 each and 0 with probability 2/3 all satisfy (4.3) with c₀(ε) = ε²/4 − ε³/6, which the paper attributes to Achlioptas (LIT-1159).
- One support (Lemma 5.1). For t = k and 0 < δ < 1, (1 − δ)‖x‖ ≤ ‖Φx‖ ≤ (1 + δ)‖x‖ on all of X_T with probability ≥ 1 − 2(12/δ)^k e^{−c₀(δ/2)n}. A δ/4-net of at most (12/δ)^k points takes (4.3) at ε = δ/2, and a least-constant bootstrap extends it from the net to the subspace.
- All supports (Theorem 5.2). A union bound over C(N, k) ≤ (eN/k)^k supports gives failure probability ≤ 2e^{−c₀(δ/2)n + k[log(eN/k) + log(12/δ)]}. So the RIP holds with the prescribed δ for every k ≤ c₁n/log(N/k), with probability ≥ 1 − 2e^{−c₂n}, where c₂ ≤ c₀(δ/2) − c₁[1 + (1 + log(12/δ))/log(N/k)]. The family counted is supports times net points, not supports alone.
- Optimality is cited, not proved. The range k ≤ C₃n/(log(N/n) + 1) is the widest possible by the Garnaev–Gluskin lower bound on the Gelfand width of the ℓ₁ ball (2.3) and Candès–Tao’s error bound (3.9).
- JL implies RIP (§6). Applying the JL lemma to Q_T with the origin added gives “a similar result with only slightly worse constants”, so a distribution that gives JL embeddings gives RIP matrices. The paper does not claim the converse.
- Universality (§6). The same proof gives the RIP for Φ(ω)Ψ for any fixed orthonormal Ψ; new for the ±1 and sparse ensembles, the authors say.
- Scope. Sufficiency only, with c₁ and c₂ left implicit. Theorem 5.2’s RIP is in squared norms while Lemma 5.1 is in unsquared ones, so the squared constant is about 2δ (an observation in the NOTE, not the paper’s).
Standing in the record
Filed on 2026-10-14 for QUESTION-120 as the bridge between two of its threads, and read the same day in NOTE-931. The compressed-sensing bound that Toy Models of Superposition proves in its appendix (NOTE-278) assumes the restricted isometry property. This paper derives that property from the concentration inequality of the simplified Johnson–Lindenstrauss proofs, with Achlioptas’s constants (LIT-1159). It cites the lemma itself to Johnson and Lindenstrauss (LIT-1153) and Dasgupta and Gupta (LIT-1157) only in a list.
The registration said “if this proof is right, the superposition bound and the lemma share their mechanism”. The proof is right. The conclusion does not follow. The superposition bound is a lower bound, m = Ω(k log(n/k)), with RIP as its hypothesis. This paper shows that random matrices meet the hypothesis once n is of order k log(N/k). What makes k log(N/k) necessary it takes from Gelfand widths, not from concentration. So for the question, the sufficient side has the proposed shape, the log of a family’s size over a squared tolerance, and the necessary side is still open.
Filed as THEORY-390.