A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

Jakob Bæk Tejs Houen; Mikkel Thorup

doi:10.4230/LIPIcs.ICALP.2023.76

A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

Jakob Bæk Tejs Houen^*, Mikkel Thorup

^*Corresponding author for this work

Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

1 Citation (Scopus)

22 Downloads (Pure)

Abstract

The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map A ∈ R^m×^u in ℓ2 that preserves distances up to distortion of 1 + ε with probability 1 − δ, where m = O(ε⁻² 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	https://doi.org/10.4230/LIPIcs.ICALP.2023.76
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

Access to Document

10.4230/LIPIcs.ICALP.2023.76Licence: CC BY

FulltextFinal published version, 753 KBLicence: CC BY

Cite this

A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. / Houen, Jakob Bæk Tejs; Thorup, Mikkel.
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. ed. / Kousha Etessami; Uriel Feige; Gabriele Puppis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 76 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Houen, JBT & Thorup, M 2023, A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. in K Etessami, U Feige & G Puppis (eds), 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023., 76, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 261, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, 10/07/2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.76

Houen JBT, Thorup M. A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. In Etessami K, Feige U, Puppis G, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. 76. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261). doi: 10.4230/LIPIcs.ICALP.2023.76

Houen, Jakob Bæk Tejs ; Thorup, Mikkel. / A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. editor / Kousha Etessami ; Uriel Feige ; Gabriele Puppis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).

@inproceedings{2500eb5017b6473bad8af9870a7c55e8,

title = "A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing",

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.",

keywords = "concentration bounds, dimensionality reduction, hashing, moment bounds",

author = "Houen, {Jakob B{\ae}k Tejs} and Mikkel Thorup",

note = "Publisher Copyright: {\textcopyright} Jakob B{\ae}k Tejs Houen and Mikkel Thorup.; 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 ; Conference date: 10-07-2023 Through 14-07-2023",

year = "2023",

doi = "10.4230/LIPIcs.ICALP.2023.76",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Kousha Etessami and Uriel Feige and Gabriele Puppis",

booktitle = "50th International Colloquium on Automata, Languages, and Programming, ICALP 2023",

}

TY - GEN

T1 - A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

AU - Houen, Jakob Bæk Tejs

AU - Thorup, Mikkel

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

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - concentration bounds

KW - dimensionality reduction

KW - hashing

KW - moment bounds

UR - http://www.scopus.com/inward/record.url?scp=85167363873&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2023.76

DO - 10.4230/LIPIcs.ICALP.2023.76

M3 - Article in proceedings

AN - SCOPUS:85167363873

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

A2 - Etessami, Kousha

A2 - Feige, Uriel

A2 - Puppis, Gabriele

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

Y2 - 10 July 2023 through 14 July 2023

ER -

A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Cite this