3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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<a$. 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.

$\endgroup$
3
  • $\begingroup$ Since $A_{ij}$ are i.i.d. , maybe we ought not substitute all of them into $A_{k1}$ since they are independent r.v. :) $\endgroup$
    – dc3506
    Commented Apr 8, 2023 at 10:34
  • $\begingroup$ 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. $\endgroup$ Commented Apr 8, 2023 at 23:10
  • $\begingroup$ Thanks for explaining! $\endgroup$
    – dc3506
    Commented Apr 9, 2023 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.