# Proof Haar matrices satisfy JL lemma

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a linear map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$: $$(1-\epsilon)\|x-y\|_2 \leq \|f(x)-f(y)\|_2 \leq (1+\epsilon)\|x-y\|_2$$

I've been trying to prove that the inequality above is satisfied if $f$ is picked using the Haar Transform as follows. Let D be a random $n\times n$ diagonal matrix with each diagonal element drawn uniformly and independently from $\{-1, 1\}$ (i.e. diagonal entries of $D$ are Rademacher random variables). Let $H$ be the standard $n\times n$ Haar matrix. Let finally $M$ be a random $k \times n$ binary matrix, such that each row $i$ has a single entry $M_{ij}$ equal to $1$ for $j$ picked uniformly at random from $\{1, \ldots, n\}$, and $M_{ij} = 0$ for all other $j$. In other words, $MH$ is equal to a random $k\times n$ matrix each of whose rows is a uniformly random row of $H$. Then the transform is defined as

$$f(y) = MHDx$$

When $f$ is picked as above, what is the probability that it satisfies the Johnson-Lindenstrauss condition for a fixed pair $x,y$ (when $f$ is given by a an appropriately scaled Gaussian matrix, the probability is $1 - \frac{1}{n^2}$)?

• two comments: why do you believe it is true, and what do you mean by mean and variance: the haar matrix is a deterministic construction. Commented Jan 31, 2014 at 22:27
• I don't understand your answer to Suresh's second comment: It sounds like you are generating Haar matrices randomly, what exactly is your procedure for doing so? (As one usually thinks of a canonical/deterministically chosen Haar matrix of a given size.)
– usul
Commented Feb 1, 2014 at 1:22
• Sorry, I was wrong about the second part of the question, so I deleted it.
– hoom
Commented Feb 1, 2014 at 18:52
• still unclear what probability of success you are talking about when everything is deterministic. the Haar transform matrix is orthogonal, so it preserves $\ell_2$ distances exactly. however, it is not a low-dimensional embedding, because the dimension stays the same. it just performs a "rotation". Commented Feb 1, 2014 at 23:10
• btw by "preserves instances exactly", i mean up to scaling Commented Feb 1, 2014 at 23:34

Your construction does not work in general for the value of $k$ given.

Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have

$$Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),$$ for $k \ll d$. Of course, in this case $\|f(y) - f(x)\|_2 = 0$ is a very bad approximation for $\|x - y\|_2 = 1$. So you almost certainly get infinite error.

This is why the Fast J-L Transform of Ailon and Chazelle uses a Walsh matrix rather than a Haar matrix: $WDx$, for $D$ picked as in your setup, is likely to have a lot of non-zero entries. This is related to the Uncertainty Principle. See also this CACM exposition.

More generally, Krahmer and Ward showed that if $M$ is a (possibly random) matrix that satisfies the restricted isometry property for submatrices of size at most $k$ (with sufficiently high probability), and $D$ is picked as above, then $f(x) = MDx$ satisfies the J-L condition for any $x, y$ with probability at least $1 - 2^{-\Omega(k)}$. This is in some sense a tight connection: a random matrix that satisfies the J-L condition for any $x, y$ with probability $1 - 2^{\Omega(k \log (n/k))}$, also satisfies the RIP property for submatrices of size up to $k$.

For more on this subject check out the lecture notes from Jelani Nelson's course. In particular, lecture 17 contains the Krahmer-Ward theorem. Lectures 9-12 introduce the JL lemma with the sparse and fast variants.

• Thank you very much for answering me. But you must multiplying the ||x-y|| with $(1+\epsilon)$ and $(1-\epsilon)$. I tested your sugested in matlab with $(\epsilon=0.5)$ and get the error=0.2 and the error bound is better than hadamard (0.5). But in theory you are right, I do not understand why the code works fine.
– hoom
Commented Feb 3, 2014 at 19:11
• It's hard to say without seeing your code, you may just be testing small examples. When $d$ is sufficiently large, $f(y)$ will be a zero vector with probability very close to 1. What values of $k$ and $d$ are you trying? Commented Feb 3, 2014 at 20:13
• You're right it does not work when matrix is huge (2048*8192), First time I've tested 512 * 512. Is there any way to improve poor energy compaction of Haar?
– hoom
Commented Feb 3, 2014 at 21:33
• How about using a Hadamard matrix as Ailon and Chazelle did? Evaluating the embedding is almost as fast as with the Haar transform, but it actually preserves distances. Hadamard matrices spread out energy (after premultiplying with random signs) Commented Feb 4, 2014 at 0:00
• I am not familiar with the Slant transform. I do not think we know any version of the JL transform that has $O(d)$ embedding time in the natural parameter ranges (e.g. for $\epsilon^{-1} = O(1)$). See my updated answer, especially the lecture notes from Jelani's course. I think this discussion is getting too lengthy for comments. Commented Feb 4, 2014 at 2:01