Paperlane

no. 16 · Tuesday 17 November 2026

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

Aur{é}lien Garivier and Emmanuel Pilliat

math.ST · v4

Abstract

The Johnson-Lindenstrauss lemma is the theoretical core of the dimensionality reduction methods based on random projections. While a standard probabilistic proof uses matrices with Gaussian entries, the computational cost of random projections can be drastically reduced by the use of simpler variables, especially if they vanish with a high probability. In this paper, we propose an elementary analysis of random projections under classical assumptions that emphasizes the key role of sub-Gaussianity: any 1-sub-Gaussian distribution with variance 1 yields the same sufficient target dimension as the Gaussian distribution. We then extend the analysis to sparse projections, with data-dependent sparsity conditions on the pairwise differences of the points, and we quantify the cost of sparsity on the target dimension. A complementary lower bound shows the limits induced by the sparsity of the data itself.

journal
Transactions on Machine Learning Research 2025
fields
Statistics Theory
pdf ↗ page arXiv:2409.06275 ↗