REVISION AND PRACTICE

The complete JL proof

On this page 3 headings

Learning goal: Connect the complete probability argument into one chain.

Conditions and notation

Exponentiate, apply Markov, factor by independence, and use the Gaussian MGF.
Control both tails for one pair, then all pairs with the union bound.
For fixed failure probability, the target dimension grows like $\log n$ divided by $\varepsilon ^{2}$ .

Map: $M = \frac{1}{k} R$ , $r_{ij} \sim N (0, 1)$ independent.
For points x, y, put $u = x - y$ ; linearity gives $M x - M y = M u =: v$ .
One measurement: $r_{i}^{⊤} u \sim N (0, ∥ u ∥^{2})$ , independent across rows (W1 L8).
Rescale: $x = \frac{k}{∥ u ∥} v \sim N (0, I_{k})$ and $∥ x ∥^{2} = \frac{k ∥ v ∥ ^{2}}{∥ u ∥ ^{2}}$ (W1 L9).
Same event: $P (∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2}) = P (∥ x ∥^{2} \geq (1 + ε) k)$ (W1 L9).
Chernoff: for $0 < λ < \frac{1}{2}$ , $P \leq \frac{E [ e ^{λ ∥ x ∥^{2}} ]}{e ^{λ (1 + ε) k}} = \frac{( 1 - 2 λ ) ^{- k /2}}{e ^{λ (1 + ε) k}}$ (Markov, independence, MGF; W2 Lesson 1).
Simplify: the Taylor step gives $\leq e^{k (2 λ^{2} - λ ε)}$ , and λ = ε/4 gives $\leq e^{- k ε^{2} /8}$ (W2 Lesson 1).
Both tails: the too-small side is bounded the same way, so one pair fails with probability $\leq 2 e^{- k ε^{2} /8}$ (W2 Lesson 2).
All pairs: union bound over fewer than n² pairs gives $P (any pair fails) \leq 2 n^{2} e^{- k ε^{2} /8}$ (W1 L5, W2 Lesson 2).
Choose k: set that ≤ δ, so $k \geq \frac{8}{ε ^{2}} ln \frac{2 n ^{2}}{δ} = O (\frac{l o g n}{ε ^{2}})$ .
With probability ≥ 1 − δ every pairwise squared distance lies within $(1 \pm ε)$ . ∎

Pick ε (allowed distortion) and δ (allowed failure chance), then compute $k = ⌈ \frac{8}{ε ^{2}} ln \frac{2 n ^{2}}{δ} ⌉$ .
Check that k is well below d, otherwise there's no gain.
Draw R (k × d) with independent N(0,1) entries once, and set $M = R / k$ .
Replace every data point x by Mx (cost: about k·d multiplications per point).
Run your distance-based algorithm (nearest neighbours, k-means, …) on the k-dimensional points.
Each distance now costs k instead of d.

Exponentiate, apply Markov, factor by independence, and use the Gaussian MGF.
Control both tails for one pair, then all pairs with the union bound.
For fixed failure probability, the target dimension grows like $\log n$ divided by $\varepsilon ^{2}$ .

YOUR STUDY PROGRESS

Finished this section? Save your progress.