6
$\begingroup$

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}$)?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jan 31 '14 at 22:27
  • 2
    $\begingroup$ 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.) $\endgroup$ – usul Feb 1 '14 at 1:22
  • $\begingroup$ Sorry, I was wrong about the second part of the question, so I deleted it. $\endgroup$ – Sarvenaz Feb 1 '14 at 18:52
  • $\begingroup$ 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". $\endgroup$ – Sasho Nikolov Feb 1 '14 at 23:10
  • $\begingroup$ btw by "preserves instances exactly", i mean up to scaling $\endgroup$ – Sasho Nikolov Feb 1 '14 at 23:34
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sarvenaz Feb 3 '14 at 19:11
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Feb 3 '14 at 20:13
  • $\begingroup$ 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? $\endgroup$ – Sarvenaz Feb 3 '14 at 21:33
  • $\begingroup$ 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) $\endgroup$ – Sasho Nikolov Feb 4 '14 at 0:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Feb 4 '14 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.