Upper bounding a inner product between gaussian Wigner matrix and a rank 2 matrix

Question

Let $W$ be a standard gaussian Wigner matrix, i.e., $W_{ij}=W_{ji}$, $W_{ii}$ is iid standard gaussian. Consider

$$\langle W,QQ^T\rangle$$

where $\langle,\rangle$ is Frobenius inner product, $Q$ is a $n\times 2$ matrix such that the $i$-row is $[\cos\theta_i,\sin\theta_i]$, and $\theta_i\in[0,2\pi]$. Thus it is equivalent to the form $$\sum_{i,j}W_{ij}\cos(\theta_i-\theta_j).$$

My question is: what is the upper bound for it? Could we obtain $$\forall Q, \langle W,QQ^T\rangle\leq n\log n?$$

If not, how small we could achieve?

Note that we need the upper bound uniformly hold for all $Q$, in other words, for all $\theta\in[0,2\pi]^n$. If we fix one $Q$, then $\langle W,QQ^T\rangle\leq n\log n$ holds with high probability.

Motivation This question comes from my research, and the bound I obtained is $n^{3/2}$ by standard $\epsilon$-net argument (discretize the region into equally spaced points, and do union bound over them), however this bound is suboptimal for my purpose. I am seeking for a better upper bound, that smaller than $n^{3/2}$. The smaller, the better. And $n\log n$ is the best.

Answer 1

$\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 Talagrand's majoring measure theorem (see for example section 3.4 in Nelson - Chaining introduction with some computer science applications for relevant definitions) we have $$ \E \sup_{q \in \{\pm 1\}^n} X_q \approx \gamma_2(\{\pm 1\}^n, d_X), \tag{1}\label{472825_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} \\ & \geq \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\ne 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 $$ \begin{split} \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) \end{split} \tag{2}\label{472825_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}\label{472825_3}$$

Combining \eqref{472825_2} and \eqref{472825_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's 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.