jl-tensorized-rowcount-bound-ahle-2020
IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma-chunk-3.md
Created 2026-08-24T17:11:14+00:00
Ahle et al. (2020) proved that c face-splitting products of independent ±1 or Gaussian JL matrices satisfy the distributional JL lemma if rows ≥ O(ε⁻² log(1/δ) + ε⁻¹ · ((1/c) log(1/δ))^c), and established a matching lower bound showing the (log 1/δ)^c dependence is unavoidable.
Summary
This pins down the exact number of compressed dimensions needed when building a Johnson-Lindenstrauss projection from c layers of simple random factors, and proves the penalty for demanding higher confidence — a power of the log of the inverse failure probability — is a fundamental limit rather than an artifact of the proof. For a system tuning compression parameters, it means stacking more random layers reduces the row count but forces the confidence guarantee to degrade polynomially with the number of layers, a tradeoff that no construction can improve upon.