License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.76
URN: urn:nbn:de:0030-drops-181281
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18128/
Go to the corresponding LIPIcs Volume Portal

Houen, Jakob Bæk Tejs ; Thorup, Mikkel

A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing

pdf-format:
LIPIcs-ICALP-2023-76.pdf (0.7 MB)

Abstract

The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map A ∈ ℝ^{m × u} in ?₂ 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.

BibTeX - Entry

@InProceedings{houen_et_al:LIPIcs.ICALP.2023.76,
  author =	{Houen, Jakob B{\ae}k Tejs and Thorup, Mikkel},
  title =	{{A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{76:1--76:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18128},
  URN =		{urn:nbn:de:0030-drops-181281},
  doi =		{10.4230/LIPIcs.ICALP.2023.76},
  annote =	{Keywords: dimensionality reduction, hashing, concentration bounds, moment bounds}
}

Keywords: dimensionality reduction, hashing, concentration bounds, moment bounds
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI