Skip to main content
6 of 9
added 4 characters in body

$\newcommand{\E}{\mathbb{E}}$ Unfortunately the upper bound $n^{3/2}$ you obtained cannot be improved. In fact $$\E \sup_{Q} \langle W, Q Q^T \rangle = \Theta(n^{3/2}).$$

First of all, note that it is enough to bound this quantity for $Z$ a matrix with independent gaussians (as opposed to a symmetric matrix), since $\sqrt{2} W = Z + Z^T + D$ where $Z$ is a matrix with independent gaussian entries, and $D$ is a diagonal matrix with entries $D_{ii} = (\sqrt{2} - 2)Z_{ii}$. It is fairly easy to bound $\mathbb{E} \sup_Q \langle D, Q Q^T \rangle \leq O(\sqrt{n})$, and since for any $Q$ we have $\langle Z^T, Q Q^T\rangle = \langle Z, Q Q^T \rangle$, we get

$$ \E \sup_Q \langle W, Q Q^T \rangle \approx \E \sup_Q \langle Z, Q Q^T \rangle $$

Moreover note that by restricting our choice to $\theta_i \in \pm \pi/2$ we can get $Q Q^T$ to be any rank one matrix of form $q q^T$ for $q \in \{\pm 1\}^n$. On the other hand, for an upper bound we can use a simple triangle inequality to get $$ \sup_{q \in \{\pm 1\}^n} \langle Z, q q^T \rangle \leq \sup_{Q} \langle Z, Q Q^T \rangle \leq 2 \sup_{q \in [\pm 1]^n} \langle Z, q q^T \rangle. $$ Let us consider now a gaussian process $X_q := \langle Z, q q^T \rangle$, for $q \in [\pm 1]^n$.

We will first show the lower bound $$ \E \sup_{q \in \{ \pm 1\}^n} X_q \gtrsim n^{3/2}, $$ and then for completeness also the upper bound $$ \E \sup_{q \in [\pm 1]^n} X_q \lesssim n^{3/2}. $$

By the Talagrands majoring measure theorem (see for example section 3.4 in chaining for relevant definitions) we have $$ \E \sup_{q \in \{\pm 1\}^n} X_q \approx \gamma_2(\{\pm 1\}^n, d_X), \tag{1} $$ where $d_X : \{\pm 1\}^n \times \{ \pm 1\}^n \to \mathbb{R}_{\geq 0}$ is a pseudo metric given by $d_X(u, v) := \sqrt{\E (X_u - X_v)^2}$.

Note that for $u, v \in \{\pm 1\}^n$, we have $$ \mathbb{E} (X_u - X_v)^2 = \|u u^T - v v^T\|_F^2, $$ where $\|A\|_F^2 := \sum_{ij} A_{ij}^2$. When $\|u\|_2 = \|v\|_2 = \theta$ an elementary calculation leads to $$ \begin{split} \|u u^T - v v^T\|_F & \approx \|u u^T - v v^T\|_{op} \\ & = \theta^2(1 - \langle u/\|u\|, v/\|v\|\rangle^2) \gtrsim \|u - v\|_2^2. \end{split} $$

Let us consider now a set $T \subset \{\pm 1\}^n$ satisfying $|T| \geq 2^{\Omega(n)}$ and $\forall u,v \in T, \|u - v\|_2 \gtrsim \sqrt{n}$ (i.e. en error-correcting code with constant rate and distance). Clearly $\gamma_2(\{\pm 1\}^n, d_X) \geq \gamma_2(T, d_X)$ and since $d_X$ on $T$ is lower bounded by a discrete metric $d_X(u,v) \geq c n \mathbf{1}[u\not=v]$, we have $\gamma_2(T, d_X) \gtrsim n \sqrt{\log |T|} \gtrsim n^{3/2}$, completing the proof of the lower bound:

$$ \E \sup_Q \langle W, Q Q^T \rangle \gtrsim \E \sup_{q\in\{\pm 1\}^n} \langle Z, q q^T \rangle \approx \gamma_2(\{\pm 1\}^n, d_X) \geq \gamma_2(T, d_X) \gtrsim n^{3/2}. $$

For the upper bound, a simple calculation shows that

$$ d_X(u, v) = \|uu^T - v v^T\|_F \lesssim \max(\|u\|_2, \|v\|_2) \|u - v\|_2. $$

This yields $$\E \sup_{q\in[\pm 1]^n} X_q \approx \gamma_2([\pm 1]^n, d_X) \lesssim \gamma_2([\pm 1]^n, \sqrt{n} d_2) = \sqrt{n} \gamma_2([\pm 1]^n, d_2) \tag{2}$$ where $d_2(u, v) = \|u - v\|_2$.

Finally, applying the majorizing measures theorem again, we know that $\gamma_2([\pm 1]^n, d_2) \approx \E \sup_{q \in [\pm 1]^n} \langle q, G \rangle$, where $G$ is a gaussian vector in $\mathbb{R}^n$.

This gives $$\gamma_2([\pm 1]^n, d_2) \approx \E \sup_{q \in [\pm 1]^n} \langle q, G \rangle = \E \|G\|_1 \approx n.\tag{3}$$

Combining (2) and (3) yields the desired upper bound $$ \E \sup_Q \langle W, Q Q^T \rangle \lesssim \E \sup_{q \in [\pm 1]^n} X_q \lesssim n^{3/2}. $$

Note: Most (probably all) of this argument can be shown without resorting to the full majorizing measures theorem, and only using some consequences of this theorem, which are by themselves significantly easier to prove from scratch, like Sudakov inequality or Slepian's lemma.

I personally find it easier to think about those problems geometrically using the generic chaining/majorizing measures machinery. After figuring out the correct answer one can later trace back if the majorizing measures theorem can be subsituted for some weaker statements --- if one for some reason finds it more aesthetically pleasing to avoid using powerful tools.