Dimensionality reduction: Johnson-Lindenstrauss lemma for structured random matrices

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

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

Let $k=O(\varepsilon^{-2}\log n)$ be a natural number. Then there exists a (linear) mapping $f:\mathbb{R}^d\to \mathbb{R}^k$ such that $$ (1-\varepsilon)||x_i-x_j||_22\le ||f(x_i)-f(x_j)||_22\le (1+\varepsilon)||x_i-x_j||_22 $$ 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(\varepsilon^{-2}\log^3n)$. 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(\varepsilon^{-2}\log^2n)$. 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.