Optimal bound for operator norm of a random matrix

Question

I'm trying to solve Exercise 4.4.7 in Vershynin's book high-dimensional probability: suppose that $A$ is an $m\times n$ random matrix whose entries $A_{ij}$ are independent sub-gaussian random variables with zero means and unit variances, prove that $$ \mathbb{E}\|A\| \geq C(\sqrt{M}+\sqrt{N}), $$ where $C$ is a suitable absolute positive constant, and $\|\cdot\|$ is the operator norm of $A$. In this context, the operator norm of an $m\times n$ matrix $A$ is defined as $$ \|A\| := \max_{\|x\|_2=1}{\|Ax\|_2}, $$ where $\|\cdot\|$ is the Euclidean norm of $\mathbb{R}^N$. I observe that $\|A\| \geq \|A_{\cdot1}\|_2$, $\|A\| \geq \|A_{1\cdot}\|_2$ (where $A_{1\cdot}$ and $A_{\cdot 1}$ are respectively the first row and the first column of $A$), and that $$ \mathbb{E}(\|A_{1\cdot}\|_2^2) = N,\\ \mathbb{E}(\|A_{\cdot 1}\|_2^2) = M. $$ Thus, I would like to write something like this: $$ \mathbb{E}\|A\| \geq \mathbb{E}[\|A\|\mathbb{1}(\|A\| \leq CK(\sqrt{N}+\sqrt{M} +t))] \geq \ldots \geq C\left[\sqrt{\mathbb{E}(\|A_{1\cdot}\|_2^2)} + \sqrt{\mathbb{E}(\|A_{\cdot 1}\|_2^2)}\right]\mathbb{P}(\|A\| \leq CK(\sqrt{N}+\sqrt{M}+t)) \geq C(\sqrt{N}+\sqrt{M})(1-2e^{-t^2}), $$ where $K:=\max_{ij}\|A_{ij}\|_{\psi_2}$; the last inequality follows from Theorem 4.4.5 in Vershynin's book.

I need some hints to complete the chain of inequalities above. Thank you for your attention!

--- Edit: I found that the statement was incorrect. Consider the following sequence $\{X_n\}_{n\in\mathbb{N}}$ of random variables distributed as follows: $$ \mathbb{P}\left(X_n = \pm\frac{1}{\sqrt{n}}\right) = \frac{n}{2(n+1)},\quad \mathbb{P}\left(X_n = \pm \sqrt{n}\right) = \frac{1}{2(n+1)}. $$ By easy computation it turns out that $\mathbb{E}(X_n) = 0$ and $\mathbb{V}(X_n) = 1$. Since the $X_n$'s are bounded, they are sub-gaussian random variables. It is easy to show that the sequence converges to $0$ in $L^1$-norm: $$ \mathbb{E}(|X_n|) = \frac{1}{\sqrt{n}}\cdot\frac{n}{n+1} + \sqrt{n}\cdot\frac{1}{n+1} = \frac{2\sqrt{n}}{n+1} \longrightarrow 0. $$ Now, consider a sequence of $M\times N$ random matrices $A^{(n)}$ whose entries $A_{ij}^{(n)}$ are independent random variables distributed as above. Such matrices satisfy the assumptions of Exercise 4.4.7. However, the expectation of their operator norm converges to $0$: $$ \mathbb{E}(\|A^{(n)}\|) \leq \sum_{i=1}^N\sum_{j=1}^M \mathbb{E}(|A_{ij}^{(n)}|) = \frac{2\sqrt{n}(M+N)}{n+1} \longrightarrow 0, $$ in contradiction with the statement of the exercise.

Answer 1

I suspect there might be an "issue" in your counterexample, in that, in the limit, the random variables are unbounded. I use quotes around "issue" because the exercise statement was confusing (and slightly wrong), so he revised it in the online copy of the book: https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf.

The statement now asks you to show that, for sufficiently large m and n, $E(\Vert A \Vert) \geq \frac{1}{4}(\sqrt{m} + \sqrt{n})$. It's easy to see that $\Vert A \Vert \geq \max\{\Vert A_{1 \cdot} \Vert_2, \Vert A_{\cdot 1}\Vert_2\}$, so $\Vert A \Vert \geq \frac{1}{2}\big(\Vert A_{1\cdot}\Vert_2 + \Vert A_{\cdot 1}\Vert_2 \big)$. Now use Exercise 3.1.4 (he also adds that hint now) to get, \begin{align*} E(\Vert A \Vert) &\geq \frac{1}{2}\bigg(E\big(\Vert A_{1\cdot}\Vert_2\big) + E\big(\Vert A_{\cdot 1}\Vert_2\big)\bigg) \\ & \geq \frac{1}{2}\big(\sqrt{n} + \sqrt{m} - CK^2 \big) \\ & \geq \frac{1}{4}\big( \sqrt{n} + \sqrt{m} \big) \end{align*} where the last inequality follows by choosing $n$ and $m$ sufficiently large. The absolute constant $C$ and $K$ here may be different from those that show up in Theorem 4.4.5, but that's ok.