# Optimal bound for operator norm of a random matrix

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.

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.
• doesn't $K$ depend on $m$ and $n$? Commented Feb 14, 2022 at 23:03