  We give two different and simple constructions for dimensionality reduction
in $\ell_2$ via linear mappings that are sparse: only an
$O(\varepsilon)$-fraction of entries in each column of our embedding matrices
are non-zero to achieve distortion $1+\varepsilon$ with high probability, while
still achieving the asymptotically optimal number of rows. These are the first
constructions to provide subconstant sparsity for all values of parameters,
improving upon previous works of Achlioptas (JCSS 2003) and Dasgupta, Kumar,
and Sarl\'{o}s (STOC 2010). Such distributions can be used to speed up
applications where $\ell_2$ dimensionality reduction is used.
