no. 16 · Tuesday 17 November 2026
On Sparsity and Sub-Gaussianity in the Johnson-Lindenstrauss Lemma
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