A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 753 KB, PDF document

The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map A ∈ Rm×u in ℓ2 that preserves distances up to distortion of 1 + ε with probability 1 − δ, where m = O(ε−2 log 1/δ) and each column of A has O(εm) non-zero entries. The previous analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a Ω(log 1/δ)-wise independent hash function. The main contribution of this paper is a more general analysis of the Sparse Johnson-Lindenstrauss Transform with less assumptions on the hash function. We also show that the Mixed Tabulation hash function of Dahlgaard, Knudsen, Rotenberg, and Thorup (FOCS 2015) satisfies the conditions of our analysis, thus giving us the first analysis of a Sparse Johnson-Lindenstrauss Transform that works with a practical hash function.

Original languageEnglish
Title of host publication50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
EditorsKousha Etessami, Uriel Feige, Gabriele Puppis
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2023
Article number76
ISBN (Electronic)9783959772785
DOIs
Publication statusPublished - 2023
Event50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany
Duration: 10 Jul 202314 Jul 2023

Conference

Conference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
LandGermany
ByPaderborn
Periode10/07/202314/07/2023
SponsorDeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume261
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Jakob Bæk Tejs Houen and Mikkel Thorup.

    Research areas

  • concentration bounds, dimensionality reduction, hashing, moment bounds

ID: 364498219