<p>Your construction does not work in general for the value of $k$ given. </p>

<p>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</p>

<p>$$
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.</p>

<p>This is why the <a href="http://www.cs.princeton.edu/~chazelle/pubs/FJLT-sicomp09.pdf" rel="nofollow">Fast J-L Transform</a> 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 <a href="http://www.cs.princeton.edu/~chazelle/pubs/fasterdim-ac10.pdf" rel="nofollow">CACM exposition</a>.</p>

<p>More generally, <a href="http://arxiv.org/abs/1009.0744" rel="nofollow">Krahmer and Ward</a> 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$. </p>

<p>For more on this subject check out the <a href="http://people.seas.harvard.edu/~minilek/cs229r/lec.html" rel="nofollow">lecture notes</a> from Jelani Nelson's course. In particular, <a href="http://people.seas.harvard.edu/~minilek/cs229r/lec/lec17.pdf" rel="nofollow">lecture 17</a> contains the Krahmer-Ward theorem. Lectures 9-12 introduce the JL lemma with the sparse and fast variants. </p>

CC BY-SA 3.0
2014-02-03T19:11:04.507Z
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
CC BY-SA 3.0
2014-02-03T20:13:19.510Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-02-03T21:33:02.357Z
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
CC BY-SA 3.0
2014-02-04T00:00:13.027Z
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)
Sasho Nikolov
CC BY-SA 3.0
2014-02-04T00:27:46.920Z
A $d$ dimensional vector can be multiplied by a $d \times d$ Hadamard matrix in time $O(d \log d)$.
Sasho Nikolov
CC BY-SA 3.0
2014-02-04T01:06:37.907Z
yes, but Haar performs this multiplication in O(d). Sorry, another question: What about Slant transform that has better energy compaction than Hadamard, Does it help to get better error bound?
hoom
CC BY-SA 3.0
2014-02-04T02:01:51.940Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-02-03T17:05:18.200Z
2014-02-04T01:52:12.740Z
2014-02-04T01:52:12.740Z
Sasho Nikolov
<p>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$$</p>

<p>I've been trying to prove that the inequality above is satisfied if $f$ is picked using 
the <a href="http://en.wikipedia.org/wiki/Haar_wavelet#Haar_transform"><em>Haar Transform</em></a> 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</p>

<p>$$
f(y) = MHDx
$$</p>

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

CC BY-SA 3.0
2014-01-31T22:27:59.280Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-02-01T01:22:28.600Z
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
CC BY-SA 3.0
2014-02-01T18:52:04.743Z
Sorry, I was wrong about the second part of the question, so I deleted it.
hoom
CC BY-SA 3.0
2014-02-01T23:10:16.723Z
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".
Sasho Nikolov
CC BY-SA 3.0
2014-02-01T23:34:44.037Z
btw by "preserves instances exactly", i mean up to scaling
Sasho Nikolov
CC BY-SA 3.0
2014-02-02T14:17:49.057Z
Now, It's not exact and also is deterministic. It is a type of random projection. $\mathbb{R}^k$ means only $k$ columns/rows of Haar would be saved. ex. Let $f=HD$ H is an k × k Haar matrix and D is Rademacher matrix. in this ex $pr[success] =~ ‎√(m/(k.logk))||A-A_k||_2‎$
hoom
CC BY-SA 3.0
2014-02-02T14:31:11.920Z
$pr[success]<= ‎√(m/(k.logk))||A−Ak||2 <=1-1/n^2‎ $ for $A_{m*n}$ please see "On Variants of the Johnson–Lindenstrauss Lemma"-Matoušek and "A fast randomized algorithm for the approximation of matrices‎"-Woolfe‎.
hoom
CC BY-SA 3.0
2014-02-02T23:26:49.010Z
Matousek's paper does not talk about Haar matrices. Can you please write precisely, in the question, what randomized transform you are considering. Right now the question just claims you apply the usual deterministic Haar transform, but now in the comments there is also a diagonal Rademacher matrix and you somehow pick a subset of the Haar matrix, but you are not specifying  how. This is starting to sound more like the Fast JL Transform of Ailon and Chazelle, but it is really not clear what you mean.
Sasho Nikolov
CC BY-SA 3.0
2014-02-02T23:54:29.127Z
Ok, I added it to question.
hoom
CC BY-SA 3.0
2014-02-03T00:07:54.313Z
I took the liberty to make a somewhat extensive edit, feel free to roll back if you are unhappy with it. Also, what you are doing is similar to the work of Ailon and Chazelle, who use a Fourier matrix rather than Haar.
Sasho Nikolov
<proofs><st.statistics><embeddings>
Proof Haar matrices satisfy JL lemma
hoom
# Proof Haar matrices satisfy JL lemma

(Asked by: username_0 on 2014-01-31)

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*](http://en.wikipedia.org/wiki/Haar_wavelet#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}$)?

**Tags:** proofs, st.statistics, embeddings

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.)  
> **username_0**: Sorry, I was wrong about the second part of the question, so I deleted it.  
> **username_3**: 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".  
> **username_3**: btw by "preserves instances exactly", i mean up to scaling  
> **username_0**: Now, It's not exact and also is deterministic. It is a type of random projection. $\mathbb{R}^k$ means only $k$ columns/rows of Haar would be saved. ex. Let $f=HD$ H is an k × k Haar matrix and D is Rademacher matrix. in this ex $pr[success] =~ ‎√(m/(k.logk))||A-A_k||_2‎$  
> **username_0**: $pr[success]<= ‎√(m/(k.logk))||A−Ak||2 <=1-1/n^2‎ $ for $A_{m*n}$ please see "On Variants of the Johnson–Lindenstrauss Lemma"-Matoušek and "A fast randomized algorithm for the approximation of matrices‎"-Woolfe‎.  
> **username_3**: Matousek's paper does not talk about Haar matrices. Can you please write precisely, in the question, what randomized transform you are considering. Right now the question just claims you apply the usual deterministic Haar transform, but now in the comments there is also a diagonal Rademacher matrix and you somehow pick a subset of the Haar matrix, but you are not specifying  how. This is starting to sound more like the Fast JL Transform of Ailon and Chazelle, but it is really not clear what you mean.  
> **username_0**: Ok, I added it to question.  
> **username_3**: I took the liberty to make a somewhat extensive edit, feel free to roll back if you are unhappy with it. Also, what you are doing is similar to the work of Ailon and Chazelle, who use a Fourier matrix rather than Haar.  

---

## 1 answers

### Answer by username_3 on 2014-02-03. Score: 5 | Accepted answer

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](http://www.cs.princeton.edu/~chazelle/pubs/FJLT-sicomp09.pdf) 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](http://www.cs.princeton.edu/~chazelle/pubs/fasterdim-ac10.pdf).

More generally, [Krahmer and Ward](http://arxiv.org/abs/1009.0744) 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](http://people.seas.harvard.edu/~minilek/cs229r/lec.html) from Jelani Nelson's course. In particular, [lecture 17](http://people.seas.harvard.edu/~minilek/cs229r/lec/lec17.pdf) contains the Krahmer-Ward theorem. Lectures 9-12 introduce the JL lemma with the sparse and fast variants.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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?  
> **username_0**: 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?  
> **username_3**: 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)  
> **username_3**: A $d$ dimensional vector can be multiplied by a $d \times d$ Hadamard matrix in time $O(d \log d)$.  
> **username_0**: yes, but Haar performs this multiplication in O(d). Sorry, another question: What about Slant transform that has better energy compaction than Hadamard, Does it help to get better error bound?  
> **username_3**: 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.  

---

