Exercise 5.14: Maximum Singular Value of Gaussian Random Matrices

chapter 5 Lipschitz Gaussian

(a)

This is an easy programming exercise. We leave those to the reader.

(b)

Taking the SVD decomposition $W=US{V}^{\mathrm{\top }}$, the result follows.

(c)

If the Sudakov-Fernique inequality applies, $\mathbb{E}[\underset{u,v}{sup}{Z}_{u,v}]\le \mathbb{E}[\underset{u,v}{sup}{Y}_{u,v}],$ the desired result is implied by the Jensen’s inequality: $$\begin{array}{}\text{(1)}& \mathbb{E}[\underset{u,v}{sup}{Y}_{u,v}]=\mathbb{E}[\Vert g{\Vert }_2+\Vert h{\Vert }_2]\le \sqrt{n}+\sqrt{d}.\end{array}$$

Reducing to fixed finite subsets $\{u_1,\dots ,u_N\}\subset S^{n-1}$ and $\{v_1,\dots ,v_N\}\subset S^{d-1}$, we need to show $$\begin{array}{}\text{(2)}& \mathbb{E}[(Z_{u_i,v_j}-Z_{u_k,v_l}{)}^2]\le \mathbb{E}[(Y_{u_i,v_j}-Y_{u_k,v_l}{)}^2]\end{array}$$ for any $i,j,k,l\in [N]$. Using the mutual independence of the standard normal random variables constituting $Z_{u,v}$ and $Y_{u,v}$ $$\begin{array}{}\text{(3)}& \mathbb{E}[(Z_{u_i,v_j}-Z_{u_k,v_l}{)}^2]=\Vert u_i{v}_j^{\mathrm{\top }}-u_k{v}_l^{\mathrm{\top }}{\Vert }_F^2,\text{(4)}& \mathbb{E}[(Y_{u_i,v_j}-Y_{u_k,v_l}{)}^2]=\Vert u_i-u_k{\Vert }_2^2+\Vert v_j-v_l{\Vert }_2^2.\end{array}$$ Application of the inequality derived in Exercise 5.11 implies the assumptions of the Sudakov-Fernique inequality hold. Hence $$\begin{array}{}\text{(5)}& \mathbb{E}[\underset{i,j\in [N]}{sup}{Z}_{u_i,v_j}]\le \mathbb{E}[\underset{i,j\in [N]}{sup}{Y}_{u_i,v_j}],\end{array}$$ and the desired result follows by applying the monotone convergence theorem, first on the r.h.s., then on the l.h.s.

(d)

This follows from Exercise 5.11(c), using that $$\begin{array}{}\text{(6)}& \underset{u,v}{sup}\mathbb{V}(Z_{u,v})=\underset{u,v}{sup}\mathbb{E}[(u^{\mathrm{\top }}Wv{)}^2]=\underset{u,v}{sup}\Vert u{\Vert }_2^2\Vert v{\Vert }_2^2=1,\end{array}$$ which avoids the factor of two when the one-sided version of the Lipschitz Gaussian concentration (Theorem 2.26) is applied.