matousek-sparser-jl-requires-well-spread-vectors

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

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

Matoušek (2008) proved sparser JL projections with entries ±q^{-1/2} (prob q/2) or 0 (prob 1−q) work, but only under the well-spread assumption ‖v‖∞ ≤ α (no single coordinate dominates); it does not hold for arbitrary vectors.

Summary

This result tells you that a specific family of sparse random projections is only safe to use when your input vectors have their magnitude spread fairly evenly across coordinates. If your data has a few dominant coordinates and lots of zeros, that sparsity guarantee breaks down and you need a different projection scheme.