Access Restriction

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

   Open content in new tab
Source: ACM Digital Library