random-projection-achlioptas-sparse-values
IN premise — summaries/2026/08/24/wiki-Random_projection.md
Created 2026-08-25T02:58:51+00:00
The Achlioptas sparse random projection matrix uses entries √(3/k) with probability 1/6, 0 with probability 2/3, and −√(3/k) with probability 1/6, enabling integer arithmetic.
Summary
This describes a specific way to build a dimensionality-reduction matrix where most entries are zero and the few non-zero ones take just two symmetric values, a structure deliberately chosen so that the math works out with whole numbers instead of floating-point decimals. The practical payoff is faster, cheaper computation on standard hardware without losing the statistical guarantees that make random projections reliable.