achlioptas-sparse-jl-integer-entries

IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma-chunk-2.md

Created 2026-08-24T17:11:13+00:00

Achlioptas (2003) showed a JL projection using k×n matrices with entries from {−1, 0, +1} (Radamacher) or {−√3, 0, +√3} achieves the same distance preservation guarantee as Gaussian entries, enabling integer arithmetic for database-friendly computation.

Summary

Dimensionality reduction via random projections does not require continuous Gaussian random numbers; simple discrete entries like -1, 0, and +1 preserve distances just as well. This means the whole computation can run on plain integer arithmetic, making it fast, deterministic, and drop-in compatible with database engines instead of needing floating-point libraries.