Bourgain, JeanSjoerd, DirksenNelson, Jelani2015-03-112015Jean Bourgain, Sjoerd Dirksen, Jelani Nelson. 2015. "Toward a unified theory of sparse dimensionality reduction in Euclidean space." Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015), Portland, OR, June 14-17, 2015.http://nrs.harvard.edu/urn-3:HUL.InstRepos:14117707Let \(\Phi \in \mathbb{R}^{m×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)\) given, we study settings for m,s required to ensure \(\underset {\Phi_{x \in T}} {\mathbb{E} sup} \mid || \Phi x ||^2_2 - 1 \mid < \epsilon\), i.e.\ so that \(\Phi\) preserves the norm of every \(x \in T\) simultaneously and multiplicatively up to \(1+\epsilon\). We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense \(\Phi\) having i.i.d. gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.en-USConference Paper2015-02-04Jean Bourgain, Sjoerd Dirksen, Jelani Nelson2015-03-1110.1007/s00039-015-0332-9