SECTION 07 / 10

Johnson–Lindenstrauss lemma

On this page 4 headings

Learning goal: Understand what dimensionality reduction must preserve.

Conditions to check

Big-O describes growth and does not determine a numerical target dimension without an explicit constant.
The distortion factor applies to squared distances.
A worst-case dimension guarantee can exceed the original dimension, in which case it offers no reduction.

The ideaYou have a million points, each described by 10,000 numbers.
All you care about is how far apart the points are, for example to find nearest neighbours.
JL says you can describe each point with far fewer numbers and still have every pairwise distance correct to within, say, 10 %.
The magic: how few numbers you need depends on how many points you have, not on how many numbers you started with.

JL lemmaGiven n points in a high-dimensional space $R^{d}$ and an error parameter $ε \in (0, 1)$ , there exists a mapping $f : R^{d} \to R^{k}$ with $k \in O (\frac{l o g n}{ε ^{2}})$ such that for all x, y among the n points:

(1 - ε) ∥ x - y ∥_{2}^{2} \leq ∥ f (x) - f (y) ∥_{2}^{2} \leq (1 + ε) ∥ x - y ∥_{2}^{2} .

Reading it slowly

n points in $R^{d}$ : your data set; d is huge.
f: a recipe that turns each d-dimensional point into a k-dimensional one.
ε: how much distortion you accept.
With ε = 0.1, every squared distance after mapping is between 0.9× and 1.1× the original.
$k = O (lo g n / ε^{2})$ : the new dimension.
It grows with log n (slowly) and with $1/ ε^{2}$ (halving the error needs 4× the dimensions). d does not appear at all.
"There exists" means the lemma promises such an f exists.
Lesson 8 shows that a random matrix works.

Required k vs n on log-log axes for three epsilon values — How large k must be (using the explicit constant derived in "Beyond Week 1"). Going from 100 to 10⁹ points, a 10-million-fold increase, only raises k about 4.5×.

Key statement $n = 1 0^{6}$ , $d = 10, 000$ , ε = 0.1:

k = O (\frac{lo g 1 0 ^{6}}{0. 1 ^{2}}) = O (\frac{6 lo g 10}{1/100}) \approx 20 \times 100 = 2000,

and the guarantee becomes $0.9∥ x - y ∥^{2} \leq ∥ f (x) - f (y) ∥^{2} \leq 1.1∥ x - y ∥^{2}$ , with $f (x), f (y) \in R^{2000}$ .

Check yourself

If ε halves (0.2 → 0.1), how does k change?

k ∝ 1/ε², so it multiplies by 4.

If n grows from 10⁶ to 10¹² (squared), how does k change?

log n doubles, so k (roughly) doubles.
A million times more points, only twice the dimension.

Does increasing d from 10⁴ to 10⁸ change k?

No. k does not depend on d.

Key points to remember

JL preserves squared distances approximately for a finite set of points.
The target dimension grows with $\log n$ and $1/\varepsilon ^{2}$ .
Big-O alone does not give an exact numerical dimension.

YOUR STUDY PROGRESS

Finished this section? Save your progress.

Johnson–Lindenstrauss lemma

Conditions to check #

Reading it slowly #

Check yourself #

Key points to remember #

Conditions to check

Reading it slowly

Check yourself

Key points to remember