high probability bound for operator norm of difference for Gaussian covariance matrix

Theorem

For $d < m$ , let $G \sim N (0, 1)^{\otimes d \times m}$ . Define $Δ := G G^{T} - m I_{d}$ . Then

\begin{align} \mathbb{P}[\lvert \lvert \Delta \rvert \rvert \geq 64\sqrt{ dm }] &\leq 2\exp(-d) \\ \text{and }\lvert \lvert G \rvert \rvert {#2} =\lvert \lvert GG^T \rvert \rvert &\leq m+{\cal O}(\sqrt{ dm }) \end{align}

Proof

Let $ε := \frac{1}{4}$ . Then we have:

There exists an epsilon net $X$ of $B^{d}$ where

| X | \leq {(1 + \frac{2}{ε})}^{d} = {(1 + \frac{2}{\frac{1}{4}})}^{d} = 9^{d}

We have the bound (from epsilon net restricted inner product bounds the operator norm)

| | Δ | | \leq \frac{1}{1 - 2 ε} | | Δ | |_{X} = \frac{1}{1 - 2 (\frac{1}{4})} | | Δ | |_{X} = 2 | | Δ | |_{X}

So

\begin{align} \mathbb{P}[\lvert \lvert \Delta \rvert \rvert \geq t] &\leq \mathbb{P}\left[ \lvert \lvert \Delta \rvert \rvert _{{\cal X}} \geq \frac{t}{2} \right] \\ \text{union bound} \implies &\leq \sum_{x \in{\cal X}} \mathbb{P}\left[ \underbrace{\lvert x^T\Delta x \rvert}_{GG^T - mI_{d}} \geq \frac{t}{2} \right] \\ \text{Since } x \in {\cal X} \subseteq B^d &\text{ we know } \lvert \lvert x \rvert \rvert \leq 1. \text{ So let } \hat{x}:= \frac{x}{\lvert \lvert x \rvert \rvert} \in \mathbb{S}^{d-1}\\ \\ \implies&\leq \sum_{x \in {\cal X}} \mathbb{P}\left[ \lvert \hat{x}^T \Delta \hat{x} \rvert \geq \frac{t}{2} \right] \\ &= \sum_{x \in {\cal X}} \mathbb{P}_{G}\left[ \lvert\,\lvert \lvert \underbrace{G^T\hat{x}}_{\in \mathbb{R}^m,\, \text{Law}=N(0,I_{m})} \rvert \rvert^2 - m \,\rvert \geq \frac{t}{2} \right] \\ \text{Now let }g&=G^T\hat{x} \\ \implies &= \lvert {\cal X} \rvert \cdot \mathbb{P}_{g \sim N(0, I_{m})}\left[ \lvert\,\lvert \lvert g \rvert \rvert {#2} -m \,\rvert \geq \frac{t}{2} \right] \\ &\leq 9^d\cdot 2\exp\left( -\frac{1}{8}\min\left\{ \frac{t^2}{4m}, \frac{t}{2} \right\} \right) \\ &\leq 2\exp\left( 3d - \frac{1}{8} \min\left\{ \frac{C^2}{4}d, \underbrace{\frac{C}{2}\sqrt{ dm }}_{d\leq m \implies \sqrt{ dm } \geq d} \right\} \right) \\ [\text{set } t:= C\sqrt{ dm },\;9 \leq \exp(3)] \implies &\leq 2\exp\left( d\left[ 3- \underbrace{\min\left\{ \frac{C^2}{32}, \frac{C}{16} \right\}}_{C=64\to \min(>4, 4)} \right] \right) \\ (*) C:= 64 \to\quad&\leq 2 \exp(-d) \end{align}

For $(*)$ , we want to pick $C$ big enough that everything is negative.

\begin{matrix} ◼ \end{matrix}

Union Bound

the union bound is countable subadditivity or the fact that

P (⋃_{i} A_{i}) \leq \sum_{i} P (A_{i})

References

Mentions

File	Last Modified
dimension requirements for gaussian random matrix to be a restricted isometry with high probability	2025-09-10
high probability bound on singular values of gaussian random matrix	2025-09-05
Random Matrix Lecture 04	2025-09-09
Random Matrix Lecture 05	2025-09-11

References

See Also

Mentions