# Spectral norm of matrices of i.i.d. bounded r.v. is sub-Gaussian

The setting is $$A\in \mathbb{R}^{n*n}$$ with each entry being i.i.d. bounded r.v. in $$[a,b]$$. The question is to prove $$\Vert A\Vert_2$$ is sub-Gaussian.

Intuitively I thought 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. Is there any problem in the above process?

Yes, there's a problem.

Suppose $$v_i$$ is $$1$$ for $$i=1$$ and 0 otherwise. Then $$\sum_{i,j} v_iv_j\left(\sum_k A_{ki}A_{kj}\right)=\sum_k A_{k1}A_{k1}=\sum_k A_{k1}^2$$ and this is only bounded above by $$\max (na^2, nb^2)$$. Looking for a deterministic bound won't work; it doesn't take advantage of the randomness.

Next, simple computer experiments show that $$\|A\|_2$$ is large when $$n$$ is large, so we should expect even the probabilistic bounds to depend on $$n$$. Also, there are two definitions of sub-Gaussian out there, one requiring zero mean and one not. We must be using the one that doesn't, since $$\|A\|_2$$ clearly doesn't have zero mean.

Given the bounds $$[a,b]$$ and no other information, we're presumably supposed to use Hoeffding's inequality. To reduce the number of cases to consider, I'll assume $$0. An obvious iid sum to apply the inequality to is the Frobenius norm $$\|A\|_F^2=\sum_{ij} A_{ij}^2$$.

By Hoeffding's inequality $$P(|\|A\|_F^2-E[\|A\|_F^2]|>t)\leq 2\exp\frac{-2t^2}{n^2(b^2-a^2)^2}$$ so $$\|A\|_F^2$$ is sub-Gaussian and so $$\left\|\|A\|_F\right\|_{\psi_2}$$ is finite, where $$\|X\|_{\psi_2}=\inf\left\{C>0: E[ \exp(|X/C|^2)]\leq 2 \right\}$$

Now $$0\leq\|A\|_2\leq \|A\|_F$$ implies $$\|A\|_2$$ also has finite $$\psi_2$$ norm and is sub-Gaussian.

• Since $A_{ij}$ are i.i.d. , maybe we ought not substitute all of them into $A_{k1}$ since they are independent r.v. :) Commented Apr 8, 2023 at 10:34
• There are $n$ summands, each of which is bounded by $a^2$ or $b^2$, so if you want a bound, it's $nb^2$ or $na^2$. The typical value will be smaller, which is the whole point of the problem, but you were claiming a deterministic bound. Commented Apr 8, 2023 at 23:10
• Thanks for explaining! Commented Apr 9, 2023 at 13:35