This is an announcement for the paper “On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms” by Casper Benjamin Freksenhttps://arxiv.org/find/math/1/au:+Freksen_C/0/1/0/all/0/1, Kasper Green Larsenhttps://arxiv.org/find/math/1/au:+Larsen_K/0/1/0/all/0/1.
Abstract: The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that for any set of vectors $X\subset R^n$, there exists a mapping $f: X\rightarrow R^M$ such that $f(X)$ preserves all pairwise distances between vectors in $X$ to within $(1\pm\epsilon)$ if $m=O(\epsilon-2lgN)$. 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-2lgN)$ dimensions has an embedding time of $m=O(nlgN+\epsilon-2lg3N)$. An exciting approach towards improving this, due to Hinrichs and Vyb'iral, 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(nlgm)$ time. The big question is of course whether $m=O(\epsilon-2lgN)$ 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'iral shows that $m=O(\epsilon-2lg2N)$dimensions suffices. 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(\epsilon-2lg2N)$for the Toeplitz approach to work.
The paper may be downloaded from the archive by web browser from URL https://arxiv.org/abs/1706.10110