The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping $$f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m$$ such that for any vector $$x \in {\mathbb {R}}^n$$ , f preserves its norm to within $$(1 {\pm } \varepsilon )$$ with probability $$1 - \delta $$ if $$m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))$$ . Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal $$m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))$$ dimensions has an embedding time of $${\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))$$ . An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random $$m \times n$$ Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in $${\mathcal {O}}(n \lg m)$$ time. The big question is of course whether $$m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))$$ dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that $$m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))$$ dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring $$m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))$$ for the Toeplitz approach to work.

Feature hashing, also known as {\em the hashing trick}, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix $A : \mathbb{R}^n \to \mathbb{R}^m$ (where $m \ll n$) in order to reduce the dimension of the data from $n$ to $m$ while approximately preserving the Euclidean norm. Every column of $A$ contains exactly one non-zero entry, equals to either $-1$ or $1$. Weinberger et al. showed tail bounds on $\|Ax\|_2^2$. Specifically they showed that for every $\varepsilon, \delta$, if $\|x\|_{\infty} / \|x\|_2$ is sufficiently small, and $m$ is sufficiently large, then \begin{equation*}\Pr[ \; | \;\|Ax\|_2^2 - \|x\|_2^2\; | < \varepsilon \|x\|_2^2 \;] \ge 1 - \delta \;.\end{equation*} These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters $\|x\|_{\infty} / \|x\|_2, m, \varepsilon, \delta$ remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to $1$, thus further illustrating the tightness of the presented bounds in practice.

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N, vectors X \subset R^n, there exists a mapping f : X --> R^m such that f(X) preserves all pairwise distances between vectors in X to within(1 ± \eps) if m = O(\eps^{-2} lg N). Much effort has gone into developing fast embedding algorithms, with the Fast Johnson-Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal m = O(\eps{-2}lg N) dimensions has an embedding time of O(n lg n + \eps^{-2} lg^3 N). An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random m times n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(n lg m) time. The big question is of course whether m = O(\eps^{-2} lg N) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that m = O(\eps^{-2} lg^2 N) dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exists a set of N vectors requiring m = \Omega(\eps^{-2} lg^2 N) for the Toeplitz approach to work.