Toward a unified theory of sparse dimensionality reduction in Euclidean space

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

Let $\Phi \in {\mathbb{R}}^{m\times n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $\epsilon \in (0,1/2)$ giv…