Exercise 6.8: Sub-Gaussian matrices and Mean Bounds
(a)
The following steps largely mirror the proof of Theorem 6.15. In particular, we can upper bound the MGF \begin{align} \E [e^{\lambda \gamma_{\text{max}}(S_n)}] &= \E [\gamma_{\text{max}} (e^{\lambda S_n})] \leq \tr (\E [e^{\lambda S_n}]) = \tr\bigl(\Psi_{n S_n}\bigl(\tfrac{\lambda}{n}\bigr)\bigr) \newline &\overset{\text{(i)}}{\leq} \tr \bigl[ \exp \bigl\lbrace \sum_i \log \Psi_{Q_i}\bigl(\tfrac{\lambda}{n}\bigr) \bigl\rbrace \bigr] \newline &\overset{\text{(ii)}}{\leq} \tr \bigl[ \exp \bigl\lbrace \tfrac{\lambda^2}{2 n^2} \sum_i V_i \bigl\rbrace \bigr] \newline &\overset{\text{(iii)}}{\leq} d e^{\frac{\lambda^2 \sigma^2}{2n}} \, , \end{align} where (i) is by Lemma 6.13, (ii) by the trace bound from Equation (6.25) combined with the assumed sub-Gaussianity, and (ii) by the definition \(\sigma^2 = \| \frac{1}{n} \sum_i V_i \|_2\). To obtain a bound on the expectation, we use an argument analogous to Exercise 2.12: \begin{align} \exp \lbrace \lambda \E [\gamma_\text{max}(S_n)] \rbrace \leq \E [e^{\lambda \gamma_\text{max}(S_n)}] \leq d e^{\frac{\lambda^2 \sigma^2}{2n}} \, , \end{align} implies we can take the log of both sides, divide by \(\lambda\), and set \(\lambda = \sqrt{\frac{2n}{\sigma^2}\log d}\), to obtain the desired \begin{align} \E [\gamma_\text{max}(S_n)] \leq \sqrt{\frac{2\sigma^2}{n}\log d} \, . \end{align}
(b)
Observe \begin{align} \E [e^{\lambda \| S_n \|_2}] &= \E [e^{ \lambda \max \lbrace \gamma_\text{max}(S_n) , |\gamma_\text{min}(S_n)| \rbrace }] \newline &\leq \E [ e^{\lambda \gamma_\text{max}(S_n)} + e^{-\lambda \gamma_\text{min}(S_n)} ] \newline &\leq \tr (\E[e^{\lambda \gamma_\text{max}(S_n)}]) + \tr (\E[e^{-\lambda \gamma_\text{max}(S_n)}]) \, . \end{align} As in (a), the r.h.s. can be bounded by \(2d e^{\frac{\lambda^2 \sigma^2}{2n}}\) which then yields the desired bound on the expectation.