high probability bound on singular values of gaussian random matrix

We showed the probability for this event already, so now, assuming the event happens, we just need to prove the bound.

Proof

Recall

First-order Taylor approximation (and concavity of $\sqrt{\cdot}$ ) yields

\begin{aligned} \sqrt{1 + x} & \leq 1 + \frac{x}{2} & for x \geq 0 \\ \sqrt{1 - x} & \geq 1 - x & for 0 \leq x \leq 1 \end{aligned}

| | Δ | | = | | G G^{T} - m I_{d} | | \leq 64 \sqrt{d m}

ie if the event happens, we have
(1)

\begin{aligned} σ_{1} (G) = | | G | | & = \sqrt{| | G G^{T} | |} \\ (*) & \leq \sqrt{| | m I_{d} | | + | | Δ | |} \\ \leq \sqrt{m + 64 \sqrt{d m}} \\ = \sqrt{m} \sqrt{1 + 64 \sqrt{\frac{d}{m}}} \\ (* *) & \leq \sqrt{m} (1 + \frac{64}{2} \sqrt{\frac{d}{m}}) \\ = \sqrt{m} + 32 \sqrt{d} \end{aligned}

Where

Then, for $σ_{d} (G)$ , we have a similar bound.

Note that if $m - 64 \sqrt{d m} < 0$ , then $\sqrt{m} - 64 \sqrt{d} < 0$ and the result follows. So suppose $m - 64 \sqrt{d m} \geq 0$ .

(2)

\begin{aligned} σ_{d} (G) & = \sqrt{λ_{d} (G G^{T})} \\ (*) & \geq \sqrt{λ_{d} (m I_{d}) - | | Δ | |} \\ \geq \sqrt{m - 64 \sqrt{d m}} \\ = \sqrt{m} \sqrt{1 - 64 \sqrt{\frac{d}{m}}} \\ (* *) & \geq \sqrt{m} (1 - 64 \sqrt{\frac{d}{m}}) \\ = \sqrt{m} - 64 \sqrt{d} \end{aligned}

Where

\begin{matrix} ◼ \end{matrix}

References