### Sparser Johnson-Lindenstrauss TransformsSparser Johnson-Lindenstrauss Transforms

Access Restriction
Subscribed

 Author Kane, Daniel M ♦ Nelson, Jelani Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Dimensionality reduction ♦ Johnson-Lindenstrauss ♦ Numerical linear algebra ♦ Streaming algorithms Abstract We give two different and simple constructions for dimensionality reduction in $ℓ_{2}$ via linear mappings that are sparse: only an $\textit{O}(\textit{ϵ})-fraction$ of entries in each column of our embedding matrices are non-zero to achieve distortion 1 + $\textit{ϵ}$ 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 [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where $ℓ_{2}$ dimensionality reduction is used. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 1 Page Count 23 Starting Page 1 Ending Page 23

#### Open content in new tab

Source: ACM Digital Library