4
$\begingroup$

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.

$\endgroup$
2
+100
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)}.$$ $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '19 at 0:45
  • $\begingroup$ "Moment conditions" on the second page. $\endgroup$ – d.k.o. Feb 17 '19 at 0:46
  • $\begingroup$ My bad. I've confused it with definition 2.1.1. Excuse me. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '19 at 0:47
  • $\begingroup$ I realized that I got $\sqrt{n\times m}$ instead of $\sqrt{n+m}$ which appears in your inequality. $\endgroup$ – d.k.o. Feb 17 '19 at 0:51
  • $\begingroup$ 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}$. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '19 at 0:55
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.