# Upper bound on expected norm of subgaussian random matrix

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.

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

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.

• I think you mean the maximal inequalities in Thm 2.2.1. Note that the $X_i$'s are of degree one in these inequalities. $$E[\max_i X_i] \le \sigma \sqrt{2 \log(N)}.$$ Feb 17, 2019 at 0:45
• "Moment conditions" on the second page.
– user140541
Feb 17, 2019 at 0:46
• My bad. I've confused it with definition 2.1.1. Excuse me. Feb 17, 2019 at 0:47
• I realized that I got $\sqrt{n\times m}$ instead of $\sqrt{n+m}$ which appears in your inequality.
– user140541
Feb 17, 2019 at 0:51
• Thanks for reminding me $||.||_op \le ||.||_F$, but I don't think the later can be used since we have $\sqrt{m+n}$ on the RHS instead of the much greater $\sqrt{mn}$. Feb 17, 2019 at 0:55

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)}$$