Back to Search Start Over

Sparser Johnson-Lindenstrauss Transforms.

Sparser Johnson-Lindenstrauss Transforms.

Authors :
KANE, DANIEL M.
NELSON, JELANI
Source :
Journal of the ACM; Jan2014, Vol. 61 Issue 1, p4-23, 23p
Publication Year :
2014

Abstract

We give two different and simple constructions for dimensionality reduction in l<subscript>2</subscript> via linear mappings that are sparse: only an (ε)-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1+ε 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 l<subscript>2</subscript> dimensionality reduction is used. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00045411
Volume :
61
Issue :
1
Database :
Complementary Index
Journal :
Journal of the ACM
Publication Type :
Academic Journal
Accession number :
94300612
Full Text :
https://doi.org/10.1145/2559902