On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

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:Rn -> Rm. 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(epsilon-2lg(1/delta)) dimensions has an embedding time of O(nlgn+epsilon-2lg3(1/delta)) Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(nlgm) 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 Vybiral shows that m=O(epsilon-2lg2(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=omega(epsilon-2lg2(1/delta)) for the Toeplitz approach to work.