Sanjoy Dasgupta and Anupam Gupta (2003), “An elementary proof of a theorem of Johnson and Lindenstrauss”, Random Structures & Algorithms 22(1): 60–65 — doi:10.1002/rsa.10073
Key takeaways
From the reading, NOTE-932.
- Theorem 2.1. For any 0 < ε < 1 and integer n, if k ≥ 4(ε²/2 − ε³/3)⁻¹ ln n, then any n points V ⊂ ℝᵈ have a map f : ℝᵈ → ℝᵏ with (1 − ε)‖u − v‖² ≤ ‖f(u) − f(v)‖² ≤ (1 + ε)‖u − v‖² for all u, v ∈ V, found in randomized polynomial time.
- The map. Projection onto a random k-dimensional subspace, scaled by √(d/k). Gaussians are used only to sample a uniform unit vector in the analysis. If d ≤ k the theorem is called trivial.
- Lemma 2.2. For k < d and L the squared length of the first k coordinates of a uniform unit vector, Pr[L ≤ βk/d] for β < 1 and Pr[L ≥ βk/d] for β > 1 are each at most β^{k/2}(1 + (1 − β)k/(d − k))^{(d−k)/2} ≤ exp((k/2)(1 − β + ln β)).
- The proof. Markov’s inequality on exp{t(kβ Σ_{i≤d}Xᵢ² − d Σ_{i≤k}Xᵢ²)}, with E[e^{sX²}] = 1/√(1 − 2s), optimized at t₀ = (1 − β)/(2β(d − kβ)). The paper does not call the variable χ².
- Where the constant comes from. The lower tail is at most exp(−kε²/4) and the upper tail at most exp(−k(ε²/2 − ε³/3)/2); the upper tail sets (2.1). Each pair fails with probability at most 2/n², so over C(n, 2) pairs the map works with probability at least 1/n, and O(n) repetitions give a constant.
- Context the paper gives. Frankl and Maehara needed k = 9(ε² − 2ε³/3)⁻¹ ln n + 1. Indyk–Motwani’s Gaussian matrix needs k larger by roughly O(log log n); Achlioptas’s ±1 matrix gets the same k as Theorem 2.1. Alon’s Ω(log n/(ε² log 1/ε)) makes the result “essentially tight”. These are reported, not proved.
Standing in the record
Filed on 2026-10-14 with LIT-1153 for QUESTION-120, and read the same day in NOTE-932. It gives the lemma’s explicit dimension, and its proof shows the shape the question proposes: a per-pair tail exponentially small in k, and a union bound over a family of about n² pairs, so k is about 2 ln(n²) over a squared tolerance.
The registration said its concentration step is “the one Baraniuk et al. (LIT-1156) turn into the restricted isometry property”. The reading makes that imprecise. This paper’s step is for a projection onto a random subspace. The independent-entry matrices a RIP proof works with are the constructions it credits to Indyk and Motwani (LIT-1106, whose Gaussian proof is read in NOTE-905, Appendix A) and to Achlioptas (LIT-1159). The reading of Baraniuk et al. settles which exponent they use: Achlioptas’s, c₀(ε) = ε²/4 − ε³/6, not this paper’s (NOTE-931). The registration also called it “the version of the proof most later work quotes”; the text cannot confirm that.
For the question’s other threads, it treats k < d only and says nothing about expand-and-threshold maps, and nothing about random features. The tightness it reports is Alon’s, short of ε⁻² log n by log(1/ε); full tightness is LIT-1154’s claim. It carries no instruction for machine-learning practice and belongs here.
Filed, with LIT-1153 and LIT-1159, as THEORY-397.