THE FAST JOHNSON–LINDENSTRAUSS TRANSFORM AND APPROXIMATE NEAREST NEIGHBORS
📜 Abstract
We introduce a new low-distortion embedding of ℓ₂ᵈ into ℓₚᴼ⁽ˡᵒᵍ ⁿ⁾ (p = 1, 2) called the fast Johnson–Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the “Heisenberg principle” of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in ℓ₁ and ℓ₂. We consider the case of approximate nearest neighbors in ℓ₂ᵈ. We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.
✨ Summary
Main contribution
The paper introduces the fast Johnson–Lindenstrauss transform (FJLT), a computationally efficient alternative to dense random Johnson–Lindenstrauss projections. It embeds a finite set of points from ℓ₂ᵈ into ℓ₁ᵏ or ℓ₂ᵏ with target dimension k = O(ε⁻² log n), while preserving norms and pairwise distances within a multiplicative factor of approximately 1 ± ε.
The transform has the form Φ = PHD, where D is a random diagonal sign matrix, H is a normalized Walsh–Hadamard transform, and P is a sparse random projection matrix. The Walsh–Hadamard/sign preconditioning spreads the mass of sparse or concentrated input vectors across coordinates. This allows the subsequent sparse projection to achieve concentration guarantees that it would not obtain on its own. The resulting application time is O(d log d + min{dε⁻² log n, ε⁻ᵖ⁻⁴ logᵖ⁺¹ n}) for p ∈ {1,2}; the d log d term comes from the fast Walsh–Hadamard transform, while the remaining work depends on the sparsity of P.
The paper applies the ℓ₁ version of the transform to approximate nearest-neighbor search in Euclidean space. Its data structure uses n^{O(ε⁻²)} storage and answers queries in O(d log d + ε⁻³ log² n) time, improving the cost of repeatedly applying dense dimension-reduction maps. The algorithm first obtains a coarse candidate using a random one-dimensional projection, then narrows the search through a bounded binary search supported by discretization and lookup tables. A separate construction improves approximate nearest-neighbor search over the Hamming cube to O((d + ε⁻² log n) log d) query time, using sparse matrix structure and finite-field linear algebra.
Influence on later research
The FJLT became a foundation for subsequent work on faster and more structured dimension-reduction methods. Later research revisited the sparse projection analysis and showed that the embedding time can be reduced further by using an even sparser matrix, together with a matching lower bound for that analysis. (arxiv.org)
The transform has also been used as a structural template for butterfly-network linear operators. A 2021 paper represented the FJLT as a butterfly network followed by coordinate projection and applied this design to reduced-parameter neural-network layers, reporting nearly linear parameter counts and empirical training and inference improvements. (proceedings.mlr.press)
FJLT constructions have additionally been incorporated into randomized numerical linear-algebra methods, including work on matrix approximation and regression, where fast embeddings reduce the cost of processing high-dimensional data. (jmlr.org)