A Sparse Johnson-lindenstrauss Transform Using Fast Hashing
Houen Jakob Bæk Tejs, Thorup Mikkel. Arxiv 2023
[Paper]
ARXIV
FOCS
Independent
The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA
2012) provides a linear dimensionality-reducing map in that preserves distances up to distortion of
with probability , where
and each column of has non-zero entries. The previous
analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a
-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.
Similar Work