Johnson-Lindenstrauss lemma for circulant matrices

Introduction

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

The evaluation of $f(x)$, where $f$ is a projection onto a random $k$ dimensional subspace, is a very time-consuming operation. Therefore, a significant effort was devoted to

simplify the algorithm to allow an easy implementation.

Achlioptas observed in , that the mapping may also be realised by a matrix, where each component is selected independently at random with a fixed distribution. This decreases the time for evaluation of $f(x)$ essentially.

An important breakthrough was achieved by Ailon and Chazelle in . Let us briefly describe their Fast Johnson-Lindenstrauss transform (FJLT). The FJLT is the product of three matrices $f(x)=PHDx$, where

$P$ is a $k\times d$ matrix, where each component is generated independently at random. In particular, $P_{i,j}\approx N(0,1)$ with probability

$H$ is the $d\times d$ normalised Hadamard matrix,

$D$ is a random $d\times d$ diagonal matrix, with each $D_{i,i}$ drawn independently from $\{-1,1\}$ with probability 1/2.

It follows, that with high probability, $f(x)$ may be calculated in time $O(d\log d+qd\varepsilon^{-2}\log n).$

We refer to for a historical overview as well as for an extensive description of the present “state of the art”.

In this note we propose another direction to approach the Johnson-Lindenstrauss lemma, namely we investigate the possibility of taking a partial circulant matrix for $f$ combined with a random $\pm 1$ diagonal matrix, see the next section for exact definitions.

This transform has a running time of $O(d\log d)$, requires less randomness ($2d$ instead of $kd$ or $(k+1)d$ used in ) and allows a simpler implementation.

Unfortunately, up to now, we were only able to prove the statement with $k=O(\varepsilon^{-2}\log^{3}n)$, compared to the standard value $k=O(\varepsilon^{-2}\log n)$. We leave the possible improvements of this bound open for further investigations.

Circulant matrices

We study the question (which to our knowledge has not been addressed in the literature before), whether $f$ in the Johnson-Lindenstrauss lemma may be chosen as a circulant matrix. Let us give the necessary notation.

Let $a=(a_{0},\dots,a_{d-1})$ be independent identically distributed random variables. We denote by $M_{a,k}$ the partial circulant matrix

Furthermore, if $\varkappa=(\varkappa_{0},\dots,\varkappa_{d-1})$ are independent Bernoulli variables, we put

Then with probability at least 2/3 the following holds

The preconditioning of $x$ using $D_{\varkappa}$ seems to be necessary and we shall comment on this point later on. Its role may be compared with the use of the random Fourier transform in .

In contrast to the above mentioned variants of the Johnson-Lindenstrauss lemma, the coordinates of $f(x)$ are now no longer independent random variables. Our approach “decouples” the dependence caused by the circulant structure. It resembles in some aspects the methods used recently in compressed sensing, cf. .

First, we recall the Lemma 1 from Section 4.1 of (cf. also Lemma 2.2 of ), which shall be useful later on.

where $a_{i}$ are i.i.d. normal variables and $\alpha_{i}$ are nonnegative real numbers. Then for any $t>0$

Furthermore, we shall use the decoupling lemma of [6, Proposition 1.9].

where $(\xi^{\prime}_{0},\dots,\xi^{\prime}_{d-1})$ denotes an independent copy of $(\xi_{0},\dots,\xi_{d-1})$.

The key role in the proof of the Johnson-Lindenstrauss lemma is played by the following estimates.

Then there is a constant $c$, independent on $k,d,\varepsilon$ and $x$, such that

Here (and any time later) the summation in the index is to be understood modulo $d$.

The decoupling of the circulant matrix is based on

We use Lemma 2.2 to estimate the diagonal term $I$.

We choose $\alpha_{i}=\displaystyle\sum_{j=0}^{k-1}x^{2}_{j+i}$ and get $||\alpha||_{1}=k,||\alpha||_{\infty}\leq 1$ and hence $||\alpha||_{2}\leq\sqrt{k}$. This leads to

We set $\varepsilon k/2=2\sqrt{kt}$, i.e. $t=\varepsilon^{2}k/16$, in (2.3) and obtain

On the other hand, if $c=5/2-\sqrt{6}>1/20$, then $\sqrt{c}+c/2=1/4$ and

for $t=c\varepsilon^{2}k$, which finally gives

Next, we estimate the moments of the off-diagonal part $II$. We use Lemma 2.3 twice, which gives

where $a^{\prime}$ and $\varkappa^{\prime}$ are independent copies of $a$ and $\varkappa$, respectively.

First, we make a substitution $v=j+i,v^{\prime}=j+i^{\prime}$ and use the Khintchine inequality with the optimal constant $c_{p}\leq\sqrt{p}$ and the random variable $\varkappa$ to obtain

Next, we involve Minkowski’s inequality with respect to $p/2\geq 1$ and Khintchine’s inequality for the random variable $\varkappa^{\prime}.$

Furthermore, the Minkowski inequality for $a$ and $a^{\prime}$ gives

If $a_{0},\dots,a_{d-1}$ are Bernoulli variables, then Khintchine’s inequality gives

as the product of two independent Bernoulli variables is again of this type.

For normal variables, we use first Khintchine’s inequality and spherical coordinates to obtain

We combine (2.7) with Stirling’s inequality and obtain

Hence, if $a_{0},\dots,a_{d-1}$ are independent Bernoulli or normally distributed variables, we may estimate

We choose $p$ by the condition $\frac{\sqrt{2}cp^{3/2}}{\sqrt{k}\varepsilon}=e^{-1}$. We may assume $c\geq 1$, which ensures that $p\leq k$ and $\frac{\sqrt{k+p}}{k}\leq\frac{\sqrt{2}}{\sqrt{k}}$, which leads to

The proof then follows by (2.1) and (2.2) combined with (2.5), (2.6) and (2.9). ∎

The proof of Theorem 2.1 follows from Lemma 2.4 by the union bound over all $\binom{n}{2}$ pairs of points.

(i) We note that (2.8) follows directly by very well known estimates of moments of Gaussian chaos, cf. . We preferred to give a simple and direct proof.

(ii) Let us also mention that Lemma 2.4 fails, if the multiplication with $D_{\varkappa}$ is omitted. Namely, let $k\leq d$ be natural numbers, let $a_{0},\dots,a_{d-1}$ be independent normal variables and let $x=\frac{1}{\sqrt{d}}(1,\dots,1)$. If $f(x)=M_{a,k}x$, then

Due to the 2-stability of the normal distribution, the variable

is again normally distributed, i.e. $b\approx N(0,1).$ Hence

depends neither on $k$ nor on $d$ and Lemma 2.4 cannot hold.

(iii) The statement of Theorem 2.1 holds also for matrices with Toeplitz structure. The proof is literally the same, only notational changes are necessary.

Acknowledgement: We thank Albrecht Böttcher for his comments to the topic. The research of Aicke Hinrichs was supported by the DFG Heisenberg grant HI 584/3-2. Jan Vybíral acknowledges the financial support provided by the FWF project Y 432-N15 START-Preis “Sparse Approximation and Optimization in High Dimensions”.

References