Spectral norm of matrices of bounded random variables

Question

Assume $A\in \mathbb{R}^{n\times n}$ with each entry being i.i.d. bounded r.v. in $[a,b]$, is $\Vert A\Vert_2$ is sub-Gaussian?

Intuitively, since $\{A_{ij}\}_{i,j=1,...,n}$ is bounded, then $$\Vert A \Vert_2 = \sup_{\Vert v \Vert = 1} \vert v^TA^TAv\vert = \sup_{\Vert v \Vert = 1}\vert\sum_{i,j}v_iv_j(\sum_k A_{ki}A_{kj})\vert\leq \max(a^2,b^2)$$

Then $\Vert A\Vert_2$ is bounded so that it is sub-Gaussian. I doubt whether there exists any problem in my guess above because sub-Gaussian is much weaker than "bounded" condition.

Answer 1

Your chain of equality is slightly off, the idea is there however. I think that the following one is correct : \begin{align*} \| A \|_2^2 &= \sup_{\| v \|_2=1} v^TA^TAv\\ &= \sup_{\|v \|_2 = 1} \left| \sum_{i,j} v_i v_j \left( \sum_{k} A_{ki} A_{kj} \right) \right|\\ &\leq \sup_{\|v \|_2 = 1} \sum_{i,j} |v_i|\cdot |v_j|\cdot \left| \sum_{k} A_{ki} A_{kj} \right|\\ &\leq n \cdot \max(a^2,b^2)\sup_{\|v \|_2 = 1} \|v\|_1^2\\ &=n^2\cdot \max(a^2, b^2) \end{align*} Note that all inequalities can be achieved ($A_{i,j}=\max(a,b)$ for all $i,j$ and $v_i=\frac{1}{\sqrt{n}}$ for all $i$) and therefore your bound cannot really be correct.

Now this yields that $0\leq \| A \|_2 \leq n\cdot\max(|a|,|b|)$, and therefore $\|A \|_2$ is a sub-Gaussian.