fjlt-sub-quadratic-projection-time
IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma-chunk-2.md
Created 2026-08-24T17:11:13+00:00
The Fast Johnson-Lindenstrauss Transform (Ailon & Chazelle 2006) computes a JL projection in O(d log d + k^{2+γ}) time using a structured matrix of permutation, subsampling, and Hadamard transforms, versus O(kd) for naive matrix-vector multiplication.
Summary
High-dimensional data can be compressed into a lower-dimensional space (while roughly preserving distances) much faster than the straightforward matrix-multiplication approach, by exploiting a clever three-step structure of permutation, random signs, and a Hadamard transform. This matters because it removes a major computational bottleneck in pipelines that repeatedly project large feature vectors, making scalable similarity search and machine learning practical at high dimensionality.