Edit this page on GitHub

STT 996 – High Dimensional Probability

Lecture 06 (Reconstructed + Expanded Notes)

1. Setup: Covariance and Spectral Decomposition

Let $X \in \mathbb{R}^n, \quad \Sigma = \mathbb{E}[X X^\top]$

Assume spectral decomposition: $\Sigma = \sum_{k=1}^n \lambda_k v_k v_k^\top$

where:

$\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \ge 0$
${v_k}_{k=1}^n$ is an orthonormal basis: $\langle v_i, v_j \rangle = 0 \ (i \neq j), \quad \|v_k\|_2 = 1$

Variational characterization of eigenvalues

For each $k$: $\lambda_k = \max_{\substack{v \perp v_1,\dots,v_{k-1} \\ \|v\|_2=1}} v^\top \Sigma v$

Quadratic form expansion

Using spectral decomposition: $v^\top \Sigma v = v^\top \left(\sum_{k=1}^n \lambda_k v_k v_k^\top \right) v = \sum_{k=1}^n \lambda_k \langle v, v_k \rangle^2$

Since $\lambda_k$ are decreasing: $v^\top \Sigma v \le \lambda_1 \sum_{k=1}^n \langle v, v_k \rangle^2$

But: $\sum_{k=1}^n \langle v, v_k \rangle^2 = \|v\|_2^2 = 1$

Thus: $v^\top \Sigma v \le \lambda_1$

(Attained at $v = v_1$)

2. Isotropic Random Vectors

Definition

A random vector $X \in \mathbb{R}^n$ is isotropic if: $\Sigma = \mathbb{E}[X X^\top] = I_n$

1D intuition

In one dimension: $X = \mu + \sigma Z, \quad Z \sim \mathcal{N}(0,1)$

Multivariate normalization (whitening)

Let: $\mathbb{E}[X] = \mu$

Then define: $Z = \Sigma^{-1/2}(X - \mu)$

Then: $\mathbb{E}[Z] = 0$

and: $\mathbb{E}[Z Z^\top] = \Sigma^{-1/2} \mathbb{E}[(X-\mu)(X-\mu)^\top] \Sigma^{-1/2} = I_n$

So $Z$ is isotropic.

Constructing $\Sigma^{-1/2}$

If: $\Sigma = \sum_{k=1}^n \lambda_k v_k v_k^\top$

then: $\Sigma^{1/2} = \sum_{k=1}^n \sqrt{\lambda_k} v_k v_k^\top$

and: $\Sigma^{-1/2} = \sum_{k=1}^n \lambda_k^{-1/2} v_k v_k^\top$

3. Characterization of Isotropy

Result

$X$ is isotropic iff: $\mathbb{E}[\langle X, v \rangle^2] = \|v\|_2^2 \quad \forall v \in \mathbb{R}^n$

Proof sketch

If $\Sigma = I$: $\mathbb{E}[\langle X, v \rangle^2] = v^\top \Sigma v = v^\top v = \|v\|^2$

Conversely, assume: $\mathbb{E}[\langle X, v \rangle^2] = \|v\|^2$

Then: $v^\top (\Sigma - I)v = 0 \quad \forall v \Rightarrow \Sigma = I$

(using eigenbasis argument)

Consequence

If $X$ is isotropic: $\mathbb{E}[\|X\|_2^2] = \sum_{i=1}^n \mathbb{E}[X_i^2] = n$

4. High-Dimensional Geometry Insight

Let $X, Y$ be independent isotropic vectors.

Then: $\mathbb{E}[\langle X, Y \rangle^2] = n$

But normalized vectors: $\tilde{X} = \frac{X}{\|X\|}, \quad \tilde{Y} = \frac{Y}{\|Y\|}$

Then: $\langle \tilde{X}, \tilde{Y} \rangle \approx 0$

because: $\|X\| \approx \sqrt{n}, \quad \|Y\| \approx \sqrt{n}$

Thus: $\langle \tilde{X}, \tilde{Y} \rangle \sim \frac{1}{\sqrt{n}} \to 0$

→ random vectors are almost orthogonal in high dimension.

5. Uniform Distribution on the Sphere

Define: $S^{n-1} = \{ x \in \mathbb{R}^n : \|x\|_2 = 1 \}$

Example: $X \sim \text{Uniform}(\sqrt{n} S^{n-1})$

How to generate

Let: $g \sim \mathcal{N}(0, I_n)$

Then: $\frac{g}{\|g\|} \sim \text{Uniform}(S^{n-1})$

and: $X = \sqrt{n} \frac{g}{\|g\|}$

Orthogonal invariance

For orthogonal $O$: $Og \overset{d}{=} g$

Thus: $\frac{Og}{\|Og\|} = \frac{Og}{\|g\|} \sim \text{Uniform}(S^{n-1})$

Key fact

\[\|g\|_2^2 \sim \chi^2_n\]

Thus: $\|g\|_2 \approx \sqrt{n}$

(concentration of measure)

6. Are Coordinates Independent?

Let: $X = \sqrt{n} \frac{g}{\|g\|}$

Then:

$X$ is isotropic
but coordinates are NOT independent

Reason:

normalization couples all coordinates

7. Projection Central Limit Theorem

Theorem

Let: $X \sim \text{Uniform}(S^{n-1}), \quad v \in S^{n-1}$

Then: $\sqrt{n} \langle X, v \rangle \xrightarrow{d} \mathcal{N}(0,1)$

Proof idea

Write: $X = \frac{g}{\|g\|}, \quad g \sim \mathcal{N}(0, I_n)$

Then: $\langle X, v \rangle = \frac{\langle g, v \rangle}{\|g\|}$

Rotate so $v = e_1$: $\langle g, v \rangle = g_1$

Thus: $\sqrt{n} \langle X, v \rangle = \frac{\sqrt{n} g_1}{\|g\|}$

Key approximation

Since: $\|g\| \approx \sqrt{n}$

we get: $\frac{\sqrt{n}}{\|g\|} \approx 1$

Thus: $\sqrt{n} \langle X, v \rangle \approx g_1 \sim \mathcal{N}(0,1)$

Making it rigorous

Define event: $E_n = \{ |\|g\| - \sqrt{n}| \le C \log n \}$