On Sparsity and Sub-Gaussianity in the Johnson-Lindenstrauss Lemma

Aurélien Garivier, Emmanuel Pilliat

We provide a simple proof of the Johnson-Lindenstrauss lemma for sub-Gaussian variables. We extend the analysis to identify how sparse projections can be, and what the cost of spar…