License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.15
URN: urn:nbn:de:0030-drops-83056
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8305/
Go to the corresponding OASIcs Volume Portal

Cohen, Michael B. ; Jayram, T.S. ; Nelson, Jelani

Simple Analyses of the Sparse Johnson-Lindenstrauss Transform

pdf-format:
OASIcs-SOSA-2018-15.pdf (0.5 MB)

Abstract

For every n-point subset X of Euclidean space and target distortion 1+eps for 0<eps<1, the Sparse Johnson Lindenstrauss Transform (SJLT) of (Kane, Nelson, J. ACM 2014) provides a linear dimensionality-reducing map f:X-->l_2^m where f(x) = Ax for A a matrix with m rows where (1) m = O((log n)/eps^2), and (2) each column of A is sparse, having only O(eps m) non-zero entries. Though the constructions given for such A in (Kane, Nelson, J. ACM 2014) are simple, the analyses are not, employing intricate combinatorial arguments. We here give two simple alternative proofs of their main result, involving no delicate combinatorics. One of these proofs has already been tested pedagogically, requiring slightly under forty minutes by the third author at a casual pace to cover all details in a blackboard course lecture.

BibTeX - Entry

@InProceedings{cohen_et_al:OASIcs:2018:8305,
  author =	{Michael B. Cohen and T.S. Jayram and Jelani Nelson},
  title =	{{Simple Analyses of the Sparse Johnson-Lindenstrauss Transform}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{15:1--15:9},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Raimund Seidel},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8305},
  URN =		{urn:nbn:de:0030-drops-83056},
  doi =		{10.4230/OASIcs.SOSA.2018.15},
  annote =	{Keywords: dimensionality reduction, Johnson-Lindenstrauss, Sparse Johnson-Lindenstrauss Transform}
}

Keywords: dimensionality reduction, Johnson-Lindenstrauss, Sparse Johnson-Lindenstrauss Transform
Collection: 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Issue Date: 2018
Date of publication: 05.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI