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.

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.