Upper bound on expected norm of subgaussian random matrix

Question

Let $A \in \cal{M}_{n \times m}(\Bbb{R})$ be a random matrix with IID subgaussian entries with variance proxy $\sigma^2$. Show that $E[||A||_{op}] \le c \sigma \sqrt{m+n}$ for a constant $c$ to be determined, where the operator norm of $A$ is induced from $\ell^2$ vector norm (i.e. given by $||A||_{op}=\sup\limits_{x \in \Bbb{R}^m} ||Ax||_2/||x||_2$).

My try:

First, observe that in the given definition of operator norm, the ratio remains the same upon multiplication of $x$ by a nonzero scalar $k$, so the supremum can be taken within the unit sphere $||u||_2=1$. $$||A||_{op} = \sup\limits_{||u||_2=1} ||Au||_2$$

Let $a_{ij}$ be the $(i,j)$-th entry of $A$ for all $i = 1,\dots,n$ and $j = 1,\dots,m$. Observe that each row of $A$ is a subgaussian vector with variance proxy $\sigma^2$ since the entries of $A$ are IID subgaussian. By definition of subgaussian vector, each entry of $Au$ is a subgaussian variable with variance proxy $\sigma^2$ since $$\sum_{j=1}^m a_{ij} u_j = (a_{i1},\dots,a_{im})\,u \text{ and } ||u||_2 = 1.$$ Therefore, $||Au||_2^2$ is the sum of square of $n$ subgaussian variables. $$\forall i = 1,\dots,n, E\left[\left(\sum_{j=1}^m a_{ij} u_j\right)^2\right] \le 4\sigma^2 \tag{moment condition}$$ Summing the above inequality on $i$, we get $E[||Au||_2^2] \le 4n\sigma^2$. Finally, I applied Jensen's inequality to get $$E[||Au||_2]\le \sqrt{E[||Au||_2^2]}\le 2\sqrt n\sigma.$$ The RHS of the above inequality is independent of $u$, so $$\sup\limits_{||u||_2=1}E[||Au||_2]\le 2\sqrt n\sigma.$$ However, I think I am in the wrong direction because there's no $m$ in the final inequality, and the $\sup$ should be inside the expectation.

Thanks for reading.

Source of the question: Exercise 2.2.7 in my lecture notes.

Answer 1

I've got some hints from my professor, who says that the proof is similar to that of the maximal inequality for Euclidean balls. I'm going to expand them into a full answer.

Use Corollary 4.2.13 in Vershynin's High-Dimensional Probability with $\epsilon = \frac12$ to conclude that

• the unit closed ball in $\Bbb{R}^n$ can be convered with $6^n$ balls $B_i = \{ g \in \Bbb{R}^n \mid ||g - x_i || \le \frac12 \}$, with $||x_i||\le1$, $i = 1,\dots 6^n$
• the unit closed ball in $\Bbb{R}^m$ can be convered with $6^m$ balls $C_j = \{ g \in \Bbb{R}^m \mid ||g - y_j || \le \frac12 \}$, with $||y_j||\le1$, $j = 1,\dots 6^m$

Use the fact that $||A||_{op} = \sup\{u^TAv \mid ||u||,||v|| \le 1\}$. Since the balls are compact, we can safely replace $\sup$ with $\max$.

$$\begin{aligned} \max_{||u||,||v|| \le 1} u^TAv &\le \max_{i = 1,\dots,6^n\\j=1,\dots,6^m} \max_{c \in B_i \\ d \in C_j}c^TAd \\ &\le \max_{i = 1,\dots,6^n\\j=1,\dots,6^m} \max_{||c||,||d|| \le \frac12} (x_i + c)^T A (y_j + d) \end{aligned}$$

The second inequality holds because each $c \in B_i$ can be expressed as the sum of the centre $x_i$ and a vector with magnitude bounded by the radius $\frac12$ of the closed ball $B_i$. We do the same thing for $d \in C_j$.

Then we get a sum of four terms. It turns out that the second and the third one can be bounded by the first one.

1. Apply the maximal inequality for $N$ subgaussian variables (Theorem 2.2.1) with $N = 6^{n+m}$. $$E\left[\max_{i = 1,\dots,6^n\\j=1,\dots,6^m} x_i^TAy_j\right] \le \sigma \sqrt{2 \log (6^{n+m})}$$
2. The 4th term is $\frac14$ of the LHS of the 1st inequality. $$\max_{||c||,||d|| \le \frac12} c^TAd \le \frac14 \max_{||u||,||v|| \le 1} u^TAv$$
3. The 2nd term can be found by applying the above splitting trick one more time. $$\max_{||c|| \le \frac12} \max_{j=1,\dots,6^m} c^TAy_j \le \frac12 \max_{i = 1,\dots,6^n\\j=1,\dots,6^m}\max_{||c||\le\frac12} (x_i+c)^T A y_j.$$ Some rearrangement and scaling with enable us to find $$\max_{||c||\le\frac12}\max_{j=1,\dots,6^m} c^TAy_j \le \max_{i = 1,\dots,6^n\\j=1,\dots,6^m} x_i^TAy_j.$$
4. By the same way, the 3rd term is also bounded by the RHS of the above inequality.

By adding them, rearranging and scaling, we'll find out that $$E[\max_{||u||,||v||\le1 u^TAv}]\le4E[\max_{i = 1,\dots,6^n\\j=1,\dots,6^m} x_i^TAy_j] \le 4 \sigma\sqrt{2(\log(6+m+n)}$$

Answer 2

Since $\|A\|_{op}\le \|A\|_F=\sqrt{\operatorname{tr}(A^{\top}A)}$, $$ \mathsf{E}\|A\|_{op}\le \mathsf{E}\sqrt{\sum_{i=1}^n\sum_{j=1}^m A_{ij}^2}\overset{(1)}{\le} \sqrt{\sum_{i=1}^n\sum_{j=1}^m \mathsf{E}A_{ij}^2}\overset{(2)}{\le} 2\sigma\sqrt{n\times m}, $$ where $(1)$ follows from Jensen's inequality and $(2)$ follows from Theorem 2.1.1 in the lecture notes.

To get a tighter bound involving $\sqrt{n+m}$, one may use the following tail bound (Theorem 4.4.5 in Vershynin, R., High-Dimensional Probability): $$ \mathsf{P}(\|A\|_{op}>CK(\sqrt{n+m}+t))\le e^{-t^2}, \quad t>0, $$ where $C>0$ is a constant and $K\equiv\inf\{t>0:\mathsf{E}\exp(A_{11}^2/t^2)\le 2\}$.

Using this bound \begin{align} \mathsf{E}\|A\|_{op}&=\int_0^{\infty}\mathsf{P}(\|A\|_{op}>t)dt\le CK\sqrt{n+m}+CK\int_{\sqrt{n+m}}^{\infty}e^{-\frac{(t-\sqrt{n+m})^2}{2}}dt \\ &=CK\left(\sqrt{n+m}+\sqrt{\pi/2}\right)\le C'K\sqrt{n+m}. \end{align}

Finally, $K$ can be found using the Orlicz condition in Theorem 2.1.1 in the lecture notes.