Exercise 6.10: Tail Bounds for Non-Symmetric Matrices
(a)
Since \(\| Q_i \|_2^2 = \| Q_i^2 \|_2\) for symmetric matrices, and \begin{align} Q_i^2 = \begin{bmatrix} A_i A_i^\top & 0 \newline 0 & A_i^\top A_i \end{bmatrix} \, , \end{align} the characteristic equation \(\det(Q_i^2 - \lambda I)\) tells us that the eigenvalues of \(Q_i^2\) are the union of eigenvalues of \(A_i A_i^\top\), and \(A_i^\top A_i\). Since these are the same \begin{align} \| Q_i \|_2 = \sqrt{\| A_i A_i^\top \|_2} = \sqrt{\| A_i^\top A_i \|_2} = \| A_i \|_2 \, . \end{align}
(b)
Since \(\E [A_i] = 0\) by assumption, \(\V (Q_i) = \E [Q_i^2]\). Then by an argument analogous to (a) \begin{align} \bigl\| \sum_i \V(Q_i) \bigr\|_2 = \max \bigl\lbrace \bigl\| \sum_i \E [A_i A_i^\top] \bigr\|_2 , \bigl\| \sum_i \E [A_i^\top A_i] \bigr\|_2 \bigr\rbrace = n \sigma^2 \, . \end{align}
(c)
Appealing to the characteristic equation as in (a), we see \(\|\! \sum_i Q_i \|_2 = \|\! \sum_i A_i \|_2\). By (a) again, \(\| Q_i \|_2 = \| A_i \|_2 \leq b\). Hence we can combine (b) with the Bernstein concentration bound from Theorem 6.17 to obtain \begin{align} \P \bigl( \bigl\| \sum_i A_i \bigr\|_2 \geq n \delta \bigr) \leq 2 (d_1 + d_2) \exp \bigl\lbrace -\tfrac{n \delta^2}{2(\sigma^2 + b \delta)} \bigr\rbrace \, , \end{align} where we used \(\rank \bigl[\sum_i \V (Q_i)\bigr] \leq d_1 + d_2\).