Abstract
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 language | English |
---|---|
Title of host publication | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |
Editors | Kousha Etessami, Uriel Feige, Gabriele Puppis |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publication date | 2023 |
Article number | 76 |
ISBN (Electronic) | 9783959772785 |
DOIs | |
Publication status | Published - 2023 |
Event | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany Duration: 10 Jul 2023 → 14 Jul 2023 |
Conference
Conference | 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 |
---|---|
Country/Territory | Germany |
City | Paderborn |
Period | 10/07/2023 → 14/07/2023 |
Sponsor | DeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 261 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:© Jakob Bæk Tejs Houen and Mikkel Thorup.
Keywords
- concentration bounds
- dimensionality reduction
- hashing
- moment bounds