Dimitris Achlioptas (2003), “Database-friendly random projections: Johnson-Lindenstrauss with binary coins”, Journal of Computer and System Sciences 66(4): 671–687 — doi:10.1016/S0022-0000(03)00025-4
Key takeaways
From the reading, NOTE-926, of a 2002 journal draft; theorem numbers are the draft’s.
- Theorem 1.1. For ε, β > 0 and k ≥ k₀ = (4 + 2β)/(ε²/2 − ε³/3) · log n, with r_ij = ±1 each with probability 1/2, or r_ij = √3 × {+1, 0, −1} with probabilities 1/6, 2/3, 1/6, the map to the rows of E = (1/√k)AR satisfies (1 − ε)‖u − v‖² ≤ ‖f(u) − f(v)‖² ≤ (1 + ε)‖u − v‖² for all pairs with probability at least 1 − n
- No loss against Gaussians (§2, Lemma 4.1). The k₀ is “exactly the same” as Dasgupta and Gupta’s Gaussian bound. For each fixed d both tail bounds are strict, so the bound is marginally better; the paper does not say by how much.
- Concentration, not symmetry (§3, Eq. 3). Any independent entries with mean 0 and variance 1 make ‖f(α)‖² unbiased. A JL embedding then needs only Pr[(1 − ε)‖α‖² ≤ ‖f(α)‖² ≤ (1 + ε)‖α‖²] ≥ 1 − 2/n^{2+β} per vector, and a union bound over the pairs.
- Each tail < exp(−(k/2)(ε²/2 − ε³/3)) (Lemma 5.1), from E exp(hQ²) ≤ 1/√(1 − 2h/d) for h ∈ [0, d/2) and E Q⁴ ≤ 3/d² (Lemma 5.2).
- The worst vector is (1, …, 1)/√d (Lemma 6.1), and its projection’s even moments are at most those of N(0, 1/d) (Lemma 6.2).
- The sparse case is limited. It zeroes 2/3 of the matrix and gives a threefold speedup, “a third of all attributes” per coordinate. The paper states without proof that more than 2/3 zeros breaks its Lemma 6.3. The draft omits that lemma’s proof for the sparse case.
- Database recipe (§1.1). Each new attribute is a difference of two sums over a random partition of the kept attributes, so the projection is one SQL aggregate per coordinate. No implementation is reported.
Standing in the record
Filed on 2026-10-14 with LIT-1153 for QUESTION-120, and read the same day in NOTE-926. Its step is from a spherically random projection to independent zero-mean, unit-variance entries with sub-Gaussian moments. For the question it is the cleanest case of a threshold that is the log of a family’s size over a squared tolerance: one fixed vector’s tail, then a union bound over the (n choose 2) pairs.
The filing said it is the step to “a sparse random matrix of small integers, which is the form random projections take in the fly olfactory circuit (LIT-1158) and in sparse distributed memory (NOTE-242)”. The reading corrects that. Its sparse ensemble is signed, mean zero and only 2/3 zeros, the most its lemma allows. The fly’s matrix is {0, 1}, nonnegative and sparser, so the theorem does not cover it. SDM’s address matrix is dense ±1, the paper’s first ensemble, but SDM keeps a thresholded neighbourhood, about which the paper says nothing. The paper bears on the question’s first thread, and on the third only by marking what the fly and SDM would need beyond it.
Filed, with LIT-1157 and LIT-1153, as THEORY-397.