Dimensionality reduction: Johnson-Lindenstrauss lemma for structured random matrices

The classical Johnson-Lindenstrauss lemma may be formulated as follows.

Let $\epsilon \in (0,\frac{1}{2})$ and let $x_1,\dots ,x_n\in {\mathbb{R}}^d$ be arbitrary points.

Let $k=O({\epsilon }^{-2}\log n)$ be a natural number. Then there exists a (linear) mapping $f:{\mathbb{R}}^d\to {\mathbb{R}}^k$ such that $$(1-\epsilon )||x_i-x_j|{|}_{2}2\le ||f(x_i)-f(x_j)|{|}_{2}2\le (1+\epsilon )||x_i-x_j|{|}_{2}2$$ for all $i,j\in \{1,\dots ,n\}.$ Here $||\cdot |{|}_2$ stands for the Euclidean norm in ${\mathbb{R}}^d$ or ${\mathbb{R}}^k$, respectively.

If $k<<d$, this means, that the cloud of points $x_1,\dots ,x_n$ may be squeezed into an Euclidean space with a much smaller dimension with only a minimal distortion of the mutual distances between the points. During the last two decades, this fact found many applications, especially in algorithms design. Therefore, one tries to develop a version of the Johnson-Lindenstrauss lemma, which would better fit the needs of the specific applications - low computational costs, low number of random bits and so on. <br />
We shall briefly discuss the original proof and the following development so far. Then we consider the possibility of using random structured matrices (the so-called circulant matrices) in connection with Johnson-Lindenstrauss lemma. It turns out, that this is indeed possible if a certain sign preconditioning is used.

Using the decomposition techniques, we were able to prove the desired result for $k=O({\epsilon }^{-2}{\log }^{3}n)$. Later on, the use of such tools as discrete Fourier transform and other rather geometrical techniques make it possible to reduce the bound on $k$ to $k=O({\epsilon }^{-2}{\log }^{2}n)$. We shall present both the approaches and emphasize the advantage of the second one.

The new results are based on the joint work with A. Hinrichs, Jena, Germany.