<p>It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they assume $d \le n$, it suffices for $s$ to satisfy $s^2 \cdot d/2≥\ln(20n^2)$, which leads to $s=c\cdot d^{-1/2} \sqrt{\log n}$ for some appropriately chosen constant c.</p>

CC BY-SA 3.0
2014-05-06T21:36:36.340Z
2014-05-06T21:36:36.340Z
david
<p>In <a href="http://www.cs.princeton.edu/~chazelle/pubs/stoc06.pdf" rel="nofollow noreferrer">Ailon's paper</a> (p.3): How $1/(20nd)$ is obtained?  </p>

<p><img src="https://i.sstatic.net/1rQrI.png" alt="enter image description here"></p>

<p><img src="https://i.sstatic.net/zP7l4.png" alt="enter image description here"></p>

<proofs><embeddings>
The random densification technique-JL lemma
hoom
# The random densification technique-JL lemma

(Asked by: username_0 on 2014-05-06)

In [Ailon's paper](http://www.cs.princeton.edu/~chazelle/pubs/stoc06.pdf) (p.3): How $1/(20nd)$ is obtained?

![enter image description here](https://i.sstatic.net/1rQrI.png)

![enter image description here](https://i.sstatic.net/zP7l4.png)

**Tags:** proofs, embeddings


---

## 1 answers

### Answer by username_1 on 2014-05-06. Score: 2 | Accepted answer

It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u\_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they assume $d \le n$, it suffices for $s$ to satisfy $s^2 \cdot d/2≥\ln(20n^2)$, which leads to $s=c\cdot d^{-1/2} \sqrt{\log n}$ for some appropriately chosen constant c.


---

