1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ doesn't $K$ depend on $m$ and $n$? $\endgroup$ Commented Feb 14, 2022 at 23:03
  • $\begingroup$ You're right. Good point. Exercise 3.1.4 b) asks if CK^2 can be replaced by o(1). If it can, then we're good. The question is, can it? $\endgroup$ Commented Feb 18, 2022 at 20:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.