SECTION 01 / 5

Week 1 recap

On this page 2 headings

Learning goal: Recall why random projection preserves squared length in expectation.

Conditions and notation

The goal (JL lemma). n points in $R^{d}$ can be mapped to $R^{k}$ , $k = O (lo g n / ε^{2})$ , so that every squared distance stays within a factor $1 \pm ε$ .
The map. $M = \frac{1}{k} R$ , where R is a k × d matrix of independent $N (0, 1)$ entries.
On average it is perfect. For a fixed vector u, $v = M u$ satisfies $E ∥ v ∥^{2} = ∥ u ∥^{2}$ .
The rescaling trick. $x = \frac{k}{∥ u ∥} v$ is a standard Gaussian vector, $x \sim N (0, I_{k})$ , and

P (∥ v ∥^{2} \geq (1 + ε) ∥ u ∥^{2}) = P (∥ x ∥^{2} \geq (1 + ε) k) .

This is the starting point for Week 2.
Week 2 shows this probability is tiny (Lesson 1), extends the result from one vector to all pairs (Lesson 2), and then looks at why it works through linear algebra (Lesson 3).

YOUR STUDY PROGRESS

Finished this section? Save your progress.