SECTION 02 / 5

Prerequisite toolkit

On this page 18 headings

Learning goal: Learn the exponential, logarithm and SVD tools needed this week.

Conditions and notation

For the upper-tail proof, choose $0 <$ λ $< \frac{1}{2}$ .
The simpler Taylor bound is valid at λ $= \varepsilon /4$ when $0 < \varepsilon < 1$ .
Orthogonal transformations can include reflections; both rotations and reflections preserve length.

Week 1's toolkit (expectation, variance, normal distribution, vectors, matrices, covariance, MLE) is still needed.
Below are the new tools this week uses, each with a tiny example.

$e^{a + b} = e^{a} e^{b}$ .
So $e^{λ (x_{1}^{2} + x_{2}^{2} + \dots + x_{k}^{2})} = e^{λ x_{1}^{2}} e^{λ x_{2}^{2}} \dots e^{λ x_{k}^{2}}$ : a sum in the exponent becomes a product.
$exp (y)$ is another way to write $e^{y}$ , used when the exponent is long.
$lo g (a^{b}) = b lo g a$ , $lo g (ab) = lo g a + lo g b$ , $lo g (1/ a) = - lo g a$ , and $e^{l o g y} = y$ .
Here "log" means the natural log (ln).
$e^{y}$ and $lo g y$ are increasing functions: if $a \geq b$ then $e^{a} \geq e^{b}$ and $lo g a \geq lo g b$ .

$(\frac{1}{0.9})^{100} = e^{100 l o g (1/0.9)} = e^{100 \times 0.1054} = e^{10.54} \approx 37, 650$ .
Turning powers into exponentials is exactly what Lesson 1 does.

The idea"My height is at least 160 cm" and "my height is at least 1.6 m" are the same statement in different units, so they have the same probability.
Applying any increasing function to both sides of an inequality gives the same event in disguise.

For any λ > 0: $∥ x ∥^{2} \geq c ⟺ λ ∥ x ∥^{2} \geq λ c ⟺ e^{λ ∥ x ∥^{2}} \geq e^{λ c}$ .
Each step can be undone (divide by λ, take log), so all three events are identical and $P$ is the same for all of them.
This is the A ⇔ B idea from Week 1, the union-bound lesson.

If $Y_{1}, \dots, Y_{k}$ are independent, then $E [Y_{1} Y_{2} \dots Y_{k}] = E [Y_{1}] E [Y_{2}] \dots E [Y_{k}]$ .
Functions of independent variables are still independent, so $e^{λ x_{1}^{2}}, \dots, e^{λ x_{k}^{2}}$ qualify when $x_{1}, \dots, x_{k}$ are independent.

Two independent dice: $E [X_{1} X_{2}] = E [X_{1}] E [X_{2}] = 3.5 \times 3.5 = 12.25$ .
Without independence this fails: for $X_{2} = X_{1}$ (the same die), $E [X_{1}^{2}] = 91/6 \approx 15.17 \neq = 12.25$ .

The ideaThe MGF $E [e^{λ X}]$ packs all the moments of X ( $E [X]$ , $E [X^{2}]$ , …) into one function.
For our proof, its job is simpler: it makes large values of X count exponentially more, which is exactly what we need to measure rare large deviations.

The Gaussian identity used in Lesson 1: if $Z \sim N (0, 1)$ and $0 < λ < \frac{1}{2}$ , then

E [e^{λ Z^{2}}] = \frac{1}{1 - 2 λ} .

For the curious: where it comes from

$E [e^{λ Z^{2}}] = \int \frac{1}{2 π} e^{λ z^{2}} e^{- z^{2} /2} d z = \int \frac{1}{2 π} e^{- (1 - 2 λ) z^{2} /2} d z$ .
This is a bell-curve integral with variance $1/ (1 - 2 λ)$ , which equals $1/ (1 - 2 λ)$ .
If $λ \geq \frac{1}{2}$ the exponent is no longer negative and the integral is infinite.
That is why λ must stay below ½.

λ = 0.1: $E [e^{0.1 Z^{2}}] = 1/ 0.8 \approx 1.118$ . λ = 0.25: $1/ 0.5 \approx 1.414$ . λ = 0.49: $1/ 0.02 \approx 7.07$ .
As λ approaches ½ it blows up.

For small y: $lo g \frac{1}{1 - y} = y + \frac{y ^{2}}{2} + \frac{y ^{3}}{3} + \dots$ .
With $y = 2 λ$ and halved:

\frac{1}{2} lo g \frac{1}{1 - 2 λ} = λ + λ^{2} + \frac{4}{3} λ^{3} + \dots \leq λ + 2 λ^{2} (true for 0 \leq λ \leq 0.342) .

λ = 0.1: left side $= \frac{1}{2} lo g (1/0.8) = 0.1116$ ; right side $= 0.1 + 0.02 = 0.12$ . ✓. λ = 0.35: left $0.602$ , right $0.595$ . ✗, too big.
The lesson's choice λ = ε/4 is always below 0.25, so it is safe.

To minimise $f (λ)$ , set $f^{'} (λ) = 0$ .
For an upward parabola $f (λ) = a λ^{2} - bλ$ (a > 0) this gives the bottom: $λ = \frac{b}{2 a}$ , $f = - \frac{b ^{2}}{4 a}$ .
A parabola is convex (bowl-shaped), so this point is the global minimum.

$f (λ) = 2 λ^{2} - λ ε$ : $f^{'} = 4 λ - ε = 0 \Rightarrow λ = ε /4$ , and $f (ε /4) = 2 \cdot \frac{ε ^{2}}{16} - \frac{ε ^{2}}{4} = \frac{ε ^{2}}{8} - \frac{ε ^{2}}{4} = - \frac{ε ^{2}}{8}$ .
This calculation gives the exponent in the tail bound.

∃ means "there exists at least one"; ∀ means "for all".
The complement (opposite) of "∃ a bad pair" is "∀ pairs are good".
So $P (all good) = 1 - P (\exists bad pair)$ .
"∃ a bad pair" is the union of the events "pair 1 is bad", "pair 2 is bad", …, so the union bound applies.
With n points there are $(2 n) = \frac{n ( n - 1 )}{2}$ pairs, which is less than $n^{2} /2$ .
For n = 1,000 that's 499,500 pairs.

"With probability at least 1 − δ" means "the guarantee fails at most a fraction δ of the time". δ = 0.01 is a 1 % chance of failure (99 % success); δ = 0.001 is 99.9 %.
You choose δ, just as you choose ε.

The ideaThe SVD separates a matrix into three operations: rotate, stretch along the axes, rotate again.
That decomposition is the singular value decomposition.

An orthonormal (orthogonal) matrix Q has $Q^{⊤} Q = I$ .
It is a rotation (possibly with a reflection): it never changes lengths, $∥ Q u ∥ = ∥ u ∥$ .
SVD: any k × d matrix is $M = U Σ V^{⊤}$ , with U a k × k orthonormal matrix, V a d × d orthonormal matrix, and Σ a k × d "diagonal" matrix with $σ_{1}, \dots, σ_{k} \geq 0$ on its diagonal and zeros elsewhere.
The $σ_{i}$ are the singular values.
Their squares $σ_{i}^{2}$ are the eigenvalues of $M M^{⊤}$ .
Useful fact: $σ_{1}^{2} + \dots + σ_{k}^{2} = \sum_{i, j} M_{ij}^{2}$ (the sum of all squared entries).

$M = [300200]$ (2 × 3) is already in SVD form: U = I, V = I, σ₁ = 3, σ₂ = 2.
It takes (a, b, c) to (3a, 2b): it stretches the first axis 3×, the second 2×, and throws the third away.
Check: 3² + 2² = 13 = sum of squared entries.

Draw $w = (w_{1}, \dots, w_{d})$ with independent $N (0, 1)$ entries and set $r = w /∥ w ∥$ .
Then r is a uniformly random unit vector: every direction is equally likely, because the bell curve looks the same from every angle.
Lesson 3's experiment uses exactly this recipe.

Each coordinate of r has $E [r_{i}^{2}] = 1/ d$ (the d squares add to 1, and they are all alike), so a typical coordinate is about $\pm 1/ d$ in size.
But individual coordinates still vary a lot: for large d, $d r_{i}$ behaves like an $N (0, 1)$ number.
What concentrates is a sum of many squares: $r_{1}^{2} + \dots + r_{k}^{2} \approx k / d$ .

For the upper-tail proof, choose $0 <$ λ $< \frac{1}{2}$ .
The simpler Taylor bound is valid at λ $= \varepsilon /4$ when $0 < \varepsilon < 1$ .
Orthogonal transformations can include reflections; both rotations and reflections preserve length.

YOUR STUDY PROGRESS

Finished this section? Save your progress.