2026-08-06T07:08:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8305 2024-03-06T10:30:17Z ddc:004 open_access

Simple Analyses of the Sparse Johnson-Lindenstrauss Transform Cohen, Michael B. Jayram, T.S. Nelson, Jelani dimensionality reduction Johnson-Lindenstrauss Sparse Johnson-Lindenstrauss Transform 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael B. Cohen and T.S. Jayram and Jelani Nelson 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.15 urn:nbn:de:0030-drops-83056 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode