A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

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

Standard

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

Harvard

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

APA

Houen, J. B. T., & 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 https://doi.org/10.4230/LIPIcs.ICALP.2023.76

Vancouver

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). https://doi.org/10.4230/LIPIcs.ICALP.2023.76

Author

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

Bibtex

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

}

RIS

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 -

ID: 364498219