SECTION 04 / 5

Preserving all pairs: the final JL guarantee

On this page 11 headings

Learning goal: Choose a target dimension that preserves every pair with high probability.

Conditions and notation

There are n(n−1)/2 distinct unordered pairs.
Use both tails and the union bound; pair failures need not be independent.
The target dimension is an integer, so round the final requirement upward.

The ideaOne coin lands heads with probability ½, but two coins both landing heads is only ¼.
Likewise, knowing that one distance survives the squeeze is not enough: we need every one of the ~n²/2 distances to survive at the same time.
The union bound adds up all the small failure chances, and because each one is exponentially small, k only needs to grow like log n to pay for all of them.

Step 1: what we have so far

Key statement

P (∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2}) = P (∥ x ∥^{2} \geq (1 + ε) k) \leq e^{- k ε^{2} /8}

Picture: n points in $R^{d}$ , one pair joined by the difference vector u, mapped by $\frac{1}{k} R$ to the pair in $R^{k}$ joined by $v = \frac{1}{k} R u$ .

Take any two points x, y and let $u = x - y$ .
Because M is linear, $M x - M y = M (x - y) = M u = v$ .
So for one fixed pair, the chance that its squared distance grows by more than (1 + ε) is at most $e^{- k ε^{2} /8}$ .
This is true for any fixed vector u.

Step 2: the real bad event

What do we really want

P (real bad event we care about \exists a pair (x_{i}, x_{j}) s.t. ∥ M x_{i} - M x_{j} ∥^{2} \geq (1 + ε) ∥ x_{i} - x_{j} ∥^{2})

= P ((2 n) pairs ⋃ {∥ M x_{i} - M x_{j} ∥^{2} \geq (1 + ε) ∥ x_{i} - x_{j} ∥^{2}})

\leq (2 n) pairs \sum P (v ∥ M x_{i} - M x_{j} ∥^{2} \geq (1 + ε) u ∥ x_{i} - x_{j} ∥^{2})

[UNION BOUND]

If even one pair is distorted, the lemma's promise fails, so the real bad event is "there exists a bad pair".
Its complement (Toolkit 0.7) is the good event: all pairs are preserved.
"There exists a bad pair" is the union of the per-pair bad events.
We don't know how these events overlap, so we use the union bound (Week 1, the union-bound lesson) and simply add their probabilities.

Step 3: add up and solve for k

Key statement

P (real bad event) \leq n^{2} e^{- k ε^{2} /8} \leq δ (e.g. δ = 0.001)

lo g (n^{2}) - \frac{k ε ^{2}}{8} \leq lo g δ ⟹ \frac{k ε ^{2}}{8} \geq lo g (n^{2}) - lo g δ = lo g \frac{n ^{2}}{δ}

⟹ k \geq \frac{8}{ε ^{2}} lo g (\frac{n ^{2}}{δ}) \leftarrow does NOT depend on d

$k \in O (lo g (n / δ) / ε^{2})$ .

Why n²? There are $(2 n) < n^{2} /2$ pairs, each failing with probability at most $e^{- k ε^{2} /8}$ .
Writing n² instead of $(2 n)$ is slightly loose but simpler.
Solving for k: take log of both sides (log is increasing), move terms across, multiply by $8/ ε^{2}$ .
Reading the result: if k is at least this big, then with probability at least 1 − δ, all pairwise distances are preserved.
If k is smaller, the proof can't promise it.
Why it's O(log(n/δ)/ε²): $lo g \frac{n ^{2}}{δ} \leq 2 lo g \frac{n}{δ}$ (when δ ≤ 1).
When δ is treated as a fixed constant, this is the familiar $O (lo g n / ε^{2})$ .

Step 4: both sides

Key statement"Similar analysis can be done to show" $P (∥ v ∥^{2} \leq (1 - ε) ∥ u ∥^{2}) \leq e^{- k ε^{2} /8}$ .
Then:

P (∥ v ∥^{2} \leq (1 - ε) ∥ u ∥^{2} or ∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2})

\leq P (too small) + P (too big) \leq 2 e^{- k ε^{2} /8}

P (real bad event) \leq 2 n^{2} e^{- k ε^{2} /8} \leq δ

⟹ k \geq \frac{8}{ε ^{2}} lo g (\frac{2 n ^{2}}{δ}) k \in O (\frac{lo g n}{ε ^{2}})

A distance can fail in two ways, too big or too small.
Each is bad, so a second union bound doubles the per-pair failure chance.
The extra 2 only adds $\frac{8}{ε ^{2}} lo g 2$ to k, which changes nothing in big-O.
This is the complete JL lemma: with this k, $M = \frac{1}{k} R$ preserves all $(2 n)$ distances within $1 \pm ε$ with probability at least 1 − δ.

Required k vs n for three epsilon values, delta 0.01 — The final recipe $k \geq \frac{8}{ε ^{2}} ln \frac{2 n ^{2}}{δ}$ with δ = 0.01. From 100 points to a billion points (10⁷× more), k only grows about 3×.

Worked example 1: a realistic data set

n = 10,000 documents, ε = 0.2 (20 % distortion allowed), δ = 0.05 (95 % confidence).

$2 n^{2} / δ = 2 \times 1 0^{8} /0.05 = 4 \times 1 0^{9}$ .
$ln (4 \times 1 0^{9}) \approx 22.11$ .
$k \geq \frac{8}{0.04} \times 22.11 = 200 \times 22.11 \approx$ 4,422.
If each document is a bag-of-words vector with d = 100,000 words, every distance becomes about 23× cheaper (100,000 ÷ 4,422 ≈ 22.6) to compute, with a 95 % guarantee on all ~50 million pairs at once.

Worked example: one million points

Given: $n = 1,000,000, \varepsilon = 0.1$ and δ $= 0.01$ .
Substitute the parameters and round the target dimension upward.

\frac{2n^2}{\delta}=2\times10^{14},\qquad \ln(2\times10^{14})\approx32.9293

k\ge800\times32.9293\quad\Longrightarrow\quad k=26{,}344

This exceeds $d = 10,000$ , so the guarantee offers no dimension reduction for that input dimension.
With $\varepsilon = 0.2$ , the same formula requires $k = 6,586$ . A much larger original dimension makes the reduction useful.

Worked example 3: how δ affects k

n = 1,000, ε = 0.2.
For δ = 0.1: $200 ln (2 \times 1 0^{7}) \approx 3, 362$ .
For δ = 0.01: $200 ln (2 \times 1 0^{8}) \approx 3, 822$ .
For δ = 0.001: $200 ln (2 \times 1 0^{9}) \approx 4, 283$ .
Each 10× improvement in confidence costs only about +460 dimensions ( $200 ln 10$ ).
Confidence is cheap.

Does it really work? A simulation

40 random points in d = 3,000 dimensions (780 pairs), ε = 0.3.
For each k we drew 200 independent random matrices and counted how often at least one pair was distorted by more than 30 %.

Measured probability that any pair fails vs k, with the bound — Measured failure chance: 100 % at k = 100, 21 % at k = 300, 4.5 % at k = 400, and 0 out of 200 trials from k = 600 onwards. The formula asks for k ≥ 922 (δ = 0.1), and the union-bound curve only drops below 1 around k ≈ 650. The guarantee is safe but conservative: it must hold for *every* possible data set.

Check yourself

Why can't we just multiply the per-pair success probabilities?

That needs the pairs' events to be independent, and they aren't: all pairs share the same matrix R (and the same points).
The union bound needs no independence.

n = 100, ε = 0.5, δ = 0.01. What k does the final formula give?

$\frac{8}{0.25} ln \frac{2 \times 1 0 ^{4}}{0.01} = 32 ln (2 \times 1 0^{6}) = 32 \times 14.51 \approx 464$ .

Round the exact requirement upward: choose k = 465.

Where in the final formula does d appear?

Nowhere. k depends only on n, ε and δ.

Rewrite "P(all pairs preserved) ≥ 0.99" in terms of the bad event.

P(at least one pair distorted) ≤ 0.01, so δ = 0.01.

Key points to remember

There are n(n−1)/2 distinct unordered pairs.
Use both tails and the union bound; pair failures need not be independent.
The target dimension is an integer, so round the final requirement upward.

YOUR STUDY PROGRESS

Finished this section? Save your progress.