# Bound on Operator norm of GOE using Gaussian comparison inequality

I am reading Book: High-Dimensional Probability-An Introduction with Applications in Data Science By Roman Vershynin. I try to do Exercise 7.3.5.

The problem is following: Given symmetric $$n \times n$$ Gaussian random matrix $$A$$ whose entries above the diagonal are independent $$N(0,1)$$ random variables, and the diagonal entries are independent $$N(0,2)$$ random variables. We are expected to use Sudakov-Fernique's inequality or Gordon’s inequality to derive the bound on operator norm of $$A$$.

My approach is to use Sudakov-Fernique's inequality since $$||A||=\max _{u \in S^{n-1}}\langle A u, u\rangle$$ we can denote first gaussian process $$X_u:=\langle A u, u\rangle,u\in T=S^{n-1}$$. I also compute the increment: $$\mathbb{E}(X_u-X_v)^2=2\sum_{i,j}(u_iu_j-v_iv_j)^2$$

But I do not know how to construct another gaussian process $$Y_u$$ which dominate $$X_u$$, i.e $$$$\mathbb{E}(X_u-X_v)^2 \leq \mathbb{E}(Y_u-Y_v)^2\quad(1)$$$$ and also satisfy $$\mathbb{E}(\sup_{u\in S^{n-1}}Y_u) \leq 2\sqrt{n}$$. I try to set $$Y_u:=2\langle u, g\rangle$$ where $$g\sim N(0,I_n)$$, by Jensen inequality we know $$\mathbb{E}(\sup_{u\in S^{n-1}}Y_u)=2\mathbb{E}(||g||_2) \leq 2\sqrt{n}$$, but I do not know how to check (1).

Can Anyone help to construct $$Y_u$$ that satisfy above mentioned two properties? Really appreciate.

My solution: Actually I already solve the problem, take $$Y_u=2\langle u,g \rangle$$.$$\mathbb{E}(Y_u-Y_v)^2=4||u-v||^2$$. We only need to show $$\sum_{i,j}(u_iu_j-v_iv_j)^2\leq 2||u-v||^2$$ It is easy to check above inequality holds: \begin{align*} LHS=||uu^T-vv^T||^2_F &=||u(u-v)^T+(u-v)v^T||^2_F\\ &\leq ||u-v||^2+||u-v||^2\quad ||u||_2=||v||_2=1\\ &= RHS \end{align*}

• I don't know how I had missed this question, I'd have helped you had I seen it! You've got it right, +1 If you wish to ask anything further in this question post I can try to be of help to you. Apr 9, 2021 at 4:07

Actually, your answer is not correct since you relied on false assertion that $$\|A\| = \max_{u\in S^{n-1}}\langle Au, u \rangle$$. You can easily see this is false by taking $$A = -I_n$$,i.e. $$\|-I_n\| = 1$$ while $$\langle -I_n u, u\rangle = -1$$. This can be fixed by making it absolute value, i.e. $$\|A\| = \max_{u\in S^{n-1}}|\langle Au, u \rangle|$$. But, unfortunately, $$|\langle Au, u \rangle|$$ is not a mean-zero Gaussian random variable any more. So, you cannot apply Sudakov-Fernique comparison inequality.

To solve this exercise, we can actually imitate the proof of Theorem 7.3.1 of Vershynin's HDP book.

Let $$X_{uv} = \langle Au, v\rangle$$. Then, $$\|A\| = \max_{u, v\in S^{n-1}}X_{uv}$$.

With this, we have

$$\begin{array} \, \mathbb{E} (X_{uv}-X_{wz})^2 &= \mathbb{E} \{\sum_{i=1}^nA_{ii}(u_iv_i-w_iz_i)+\sum_{i

The rest must be straightforward by letting $$Y_{uv} = \sqrt{2}\langle g,u \rangle + \sqrt{2}\langle h,v \rangle$$, where $$g,h \backsim N(0, I_n)$$ are independent random vectors.

The Sudakov-Fernique comparison inequality yields $$E\|A\| \leq 2\sqrt{2n}$$. Note that this is actually $$\sqrt{2}$$ multiple of the bound stated in Exercise 7.3.5. I guess Vershynin made a similar mistake as yours.

• really appreciated! Dec 14, 2021 at 0:48

What the OP has proved is in fact $$\mathbb{E} \lambda_{\max}(A) \leq 2\sqrt{n}$$, where $$\lambda_{\max}(A)$$ denotes the largest singular value of $$A$$. Let us try to get a quick bound on the operator norm from this.

Since $$A$$ and $$-A$$ has the same distribution, we know that $$\mathbb{E}\lambda_{\max}(A) = \mathbb{E}\lambda_{\max}(-A)$$, call this expectation $$\alpha$$. Then, using the fact that $$\max\{a,b\}\leq \sqrt{|a|^2+|b|^2}$$,

\begin{align*} \mathbb{E} \|A\| &= \mathbb{E} \max\{ \lambda_{\max}(A), \lambda_{\max}(-A) \}\\ &\leq \alpha + \mathbb{E} \max\{ \lambda_{\max}(A) - \alpha, \lambda_{\max}(-A) - \alpha \}\\ &\leq \alpha + \mathbb{E}\sqrt{ (\lambda_{\max}(A) - \alpha)^2 + (\lambda_{\max}(-A) - \alpha)^2 }\\ &\leq \alpha + \sqrt{ \mathbb{E}(\lambda_{\max}(A) - \alpha)^2 + \mathbb{E}(\lambda_{\max}(-A) - \alpha)^2 } \\ &=\alpha + \sqrt{ 2\mathbb{E}(\lambda_{\max}(A) - \alpha)^2} \end{align*} The key observation is to view $$\lambda_\max(A)$$ as a function of $$n(n+1)/2$$ (upper triangular) standard gaussian variables, which should concentrate around its mean $$\alpha$$. One can easily check here that $$f(A) = \lambda_\max(A)$$ is $$\sqrt{2}$$-Lipschitz on $$\mathbb{R}^{n(n+1)/2}$$ and thus by the standard concentration bound of Lipschitz functions on the Gaussian space, $$\Pr\left\{ | \lambda_{\max}(A) - \alpha | > t \right\} \leq 2\exp\left(-\frac{t^2}{2\cdot \|f\|_{\textrm{Lip}}^2}\right) = 2\exp\left(-\frac{t^2}{4}\right).$$ Integrating, we see that $$\mathbb{E} | \lambda_{\max}(A) - \alpha |^2 \leq 4\ln 2 + 4$$ Therefore $$\mathbb{E}\|A\| \leq \alpha + 2\sqrt{2(\ln 2+1)} \leq 2\sqrt{n} + 2\sqrt{2(\ln 2+1)}.$$ It might be possible to improve the additive constant by looking at a general $$p$$-th moment instead of the second moment for $$\lambda_{\max}(A)-\alpha$$ but there will be an additive constant, anyway, so I am not bothered to do that.

• sorry for late reply, thanks for this great alternative answer! Really appreciated May 30, 2022 at 10:28