2022/04/04 by Fandina, Ora Nova, Høgsgaard, Mikael Møller, Larsen, Kasper Green · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2204.01800
The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of n points in d-dimensional Euclidean space into optimal k=O(ε-2 ln n) dimensions, while preserving all pairwise distances to within a factor (1 ± ε). The Fast JL transform supports computing the embedding of a data point in O(d ln d +k ln2 n) time, where the d ln d term comes from multiplication with a d × d Hadamard matrix and the k ln2 n term comes from multiplication with a sparse k × d matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between ε, d and n. In this work, we give a surprising new analysis of the Fast JL transform, showing that the k ln2 n term in the embedding time can be improved to (k ln2 n)/α for an α= Ω(min\ε-1ln(1/ε), ln n\). The improvement follows by using an even sparser matrix. We also complement our improved analysis with a lower bound showing that our new analysis is in fact tight.