REVISION AND PRACTICE

Extension: completing the JL proof

On this page 15 headings

Learning goal: Turn a one-vector error bound into a guarantee for all point pairs.

Goal: make a large projection error unlikely

Start with k independent standard normal coordinates.
Their squared values add up to a random total S. Its expected value is k.
We want the chance of S being much larger or smaller than k to be small. Assume $0 < \varepsilon < 1$ .

\begin{aligned}S&=\|x\|^2=\sum_{i=1}^{k}x_i^2\\\mathbb{E}[S]&=k\end{aligned}

Applying Markov directly gives:

\begin{aligned}&\mathbb{P}\!\left(S\ge k(1+\varepsilon)\right)\\&\le\frac{\mathbb{E}[S]}{k(1+\varepsilon)}\\&=\frac{1}{1+\varepsilon}\end{aligned}

For $\varepsilon = 0.1$ , this upper bound is about 0.91.
That allows up to a 91% failure probability, so it is too weak for a useful accuracy guarantee.
It also does not improve as k increases.

Choose a positive number λ smaller than $\frac{1}{2}$ .
The exponential function is increasing. Transforming both sides preserves the event.

\begin{aligned}&S\ge k(1+\varepsilon)\quad\\&\Longleftrightarrow\quad e^{\lambda S}\ge e^{\lambda k(1+\varepsilon)}\end{aligned}

Now apply Markov to the positive exponential random variable:

\begin{aligned}&\mathbb{P}\!\left(S\ge k(1+\varepsilon)\right)\\&\le\frac{\mathbb{E}[e^{\lambda S}]}{e^{\lambda k(1+\varepsilon)}}\end{aligned}

S is a sum of independent squared coordinates.
The exponential of a sum is a product. Independence lets us multiply the expectations.

\mathbb{E}[e^{\lambda S}]=\prod_{i=1}^{k}\mathbb{E}[e^{\lambda x_i^2}]

For a standard normal random variable Z and λ $< \frac{1}{2}$ :

\mathbb{E}[e^{\lambda Z^2}]=(1-2\lambda)^{-1/2}

There are k identical factors, so the bound becomes:

\begin{aligned}&\mathbb{P}\!\left(S\ge k(1+\varepsilon)\right)\\&\le e^{-\lambda k(1+\varepsilon)}(1-2\lambda)^{-k/2}\end{aligned}

Minimizing the preceding expression gives:

\lambda=\frac{\varepsilon}{2(1+\varepsilon)}

Substitute this value:

\begin{aligned}&\mathbb{P}\!\left(S\ge k(1+\varepsilon)\right)\\&\le\left((1+\varepsilon)e^{-\varepsilon}\right)^{k/2}\end{aligned}

The logarithm inequality below gives a simpler, slightly looser bound:

\ln(1+\varepsilon)\le\varepsilon-\frac{\varepsilon^2}{2}+\frac{\varepsilon^3}{3}

\begin{aligned}&\mathbb{P}\!\left(S\ge k(1+\varepsilon)\right)\\&\le\exp\!\left(-\frac{k(\varepsilon^2-\varepsilon^3)}{4}\right)\end{aligned}

For a fixed $\varepsilon$ between 0 and 1, the failure bound falls exponentially as k grows.
This is the improvement that plain Markov could not give.

Applying the exponential method to the lower tail gives:

\begin{aligned}&\mathbb{P}\!\left(S\le k(1-\varepsilon)\right)\\&\le\exp\!\left(-\frac{k\varepsilon^2}{4}\right)\end{aligned}

This controls a projection that is too small. The preceding upper-tail bound controls one that is too large.

k = 1,000, ε = 0.1: bound $= e^{- 1000 \times 0.009/4} = e^{- 2.25} \approx 0.105$ .
The exact value is 0.0146, so the bound holds.
At k = 2,000 the bound is 0.011 and the exact value is 0.0011.

For one pair (x, y), take u = x − y.
The pair is distorted by more than ε (too big or too small) with probability at most $2 e^{- k (ε^{2} - ε^{3}) /4}$ .

P (some pair fails) \leq \frac{n ^{2}}{2} \cdot 2 e^{- k (ε^{2} - ε^{3}) /4} = n^{2} e^{- k (ε^{2} - ε^{3}) /4} .

This is less than 1 as soon as

k > \frac{8 ln n}{ε ^{2} - ε ^{3}} = O (\frac{lo g n}{ε ^{2}}) .

A failure probability below 1 means a good map exists, which is exactly what JL claims.
If you want it to work with high probability in practice, use, for example, $k = \frac{12 l n n}{ε ^{2} - ε ^{3}}$ ; then the failure chance is at most $n^{2} \cdot n^{- 3} = 1/ n$ .

n = 10⁶, ε = 0.1: $k > \frac{8 \times 13.82}{0.01 - 0.001} = \frac{110.5}{0.009} \approx 12, 300$ .
As noted in Lesson 6, that exceeds d = 10,000.
With d = 10⁶ (and ε = 0.2: k ≈ 3,450) the reduction is dramatic.

200 random points in d = 10,000 dimensions, giving 19,900 pairs.
We project with $M = R / k$ and compare every squared distance before and after.

How to interpret the simulation

In this run, k = 3,000 preserved all pairwise squared distances within the tolerance.
The existence bound requires about 4,710 dimensions for these parameters.
The stronger high-probability version requires about 7,060 dimensions.
A particular dataset can succeed with fewer dimensions than a worst-case guarantee requires.

Exponentiate before applying Markov to obtain a useful tail bound.
Control both tails, then use the union bound across all pairs.
More target dimensions reduce the risk; stronger accuracy requires more dimensions.

YOUR STUDY PROGRESS

Finished this section? Save your progress.