Skip to content

REVISION AND PRACTICE

Formula summary and practical checklist

On this page 2 headings

Learning goal: Select the relevant formula and check its assumptions.

Conditions and notation

Use d for the original dimension, k for the target dimension, and n for the number of points.
Choose the distortion $\varepsilon$ and allowed failure probability δ before computing k.
The guarantee concerns squared distances.

Idea	Statement	Why it matters
Mean of ‖x‖²	$E ∥ x ∥^{2} = k$ for $x \sim N (0, I_{k})$	The bad event is "≥ (1 + ε) × average"
Markov / Chebyshev	$\frac{1}{1 + ε}$ / $\frac{2}{k ε ^{2}}$	Too weak: flat, or only 1/k
Chernoff trick	$P (Y \geq a) = P (e^{λY} \geq e^{λa}) \leq E [e^{λY}] / e^{λa}$	Exponential decay in k
Gaussian MGF	$E [e^{λ Z^{2}}] = (1 - 2 λ)^{- 1/2}$ , λ < ½	Makes the expectation computable
Taylor + best λ	$\frac{1}{2} lo g \frac{1}{1 - 2 λ} \leq λ + 2 λ^{2}$ ; λ = ε/4	Gives $e^{- k ε^{2} /8}$
One pair, both sides	$P (pair fails) \leq 2 e^{- k ε^{2} /8}$	Any fixed difference vector
All pairs	$P (\exists bad pair) \leq 2 n^{2} e^{- k ε^{2} /8} \leq δ$	Union bound, no independence needed
Final k	$k \geq \frac{8}{ε ^{2}} ln \frac{2 n ^{2}}{δ} = O (\frac{l o g n}{ε ^{2}})$	No d anywhere
SVD view	$∥ M u ∥^{2} = \sum_{i \leq k} σ_{i}^{2} a_{i}^{2}$ , $σ_{i} \approx d / k$ , $\sum_{i \leq k} a_{i}^{2} \approx k / d$	Random rotation + equal stretches keep length

Key points to remember

Use d for the original dimension, k for the target dimension, and n for the number of points.
Choose the distortion $\varepsilon$ and allowed failure probability δ before computing k.
The guarantee concerns squared distances.

YOUR STUDY PROGRESS

Finished this section? Save your progress.

Back to top ↑