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

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.

$$\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.

• Thank you! what is the value of $\gamma_2(\{\pm 1\}^{n/4},d_2)$ in the lower bound $\sqrt{n} \gamma_2(\{\pm 1\}^{n/4},d_2)$? is it $\gamma_2(\{\pm 1 \}^{n/4},d_2)\approx \mathbb E\sup_{q\in\{\pm 1\}^{n/4}}\langle q,G\rangle$ where $G$ is a gaussian vector in $\mathbb R^{n/4}$? this gives $\gamma_2(\{\pm \}^{n/4},d_2)\approx \mathbb E\|G\|_1\approx n/4$? Thus the lower bound is $\sqrt{n}n^{1/4}=n^{3/4}$
– tony
Commented Jun 8 at 9:10
• I never thought about we could directly consider rank 1 matrix, which simplify the problem a lot! And about this, I have an addition information on $Q$: if $Q$ is rank 1, then $Q=1_n1_n^T$, where $1_n$ is all one n-dimensional vector. In this case, according to your answer $\mathbb E\sup \langle W,QQ^T \rangle \approx \mathbb E\sup \langle Z,QQ^T \rangle$ which concentrates on $n$. Is this correct?
– tony
Commented Jun 8 at 10:13
• Fixed a few mistakes in the proof, but the answer is correct: $n^{3/2}$ is the right grow of the supremum. We can reduce to the case where $q$ is rank one, but it is a matrix of form $Q = q q^T$ where all the entries of $q$ are between $-1$ and $1$ (for the lower bound it is enough to consider entries being either $-1$ or $1$), sup $\mathbb{E} \sup \langle Z, Q Q^T \rangle$ is actually non-trivial supremum. Commented Jun 8 at 12:28
• I still have one question out of curiosity: (1) If I understood correctly, since $Q$ is rank 2, doing svd on $Q$ and use triangular inequality gives us $\mathbb E\sup_{q\in\{-1,=1\}^n}\langle Z,QQ^T \rangle\leq 2 \mathbb E\sup_{q\in[-1,+1]}\langle Z,qq^T \rangle$. Is there another way to argue it? In some cases, $QQ^T$ is replaced by a certain $f(QQ^T)$, which is not rank two.
– tony
Commented Jun 8 at 17:12
• Thank you so much! Since $n\sqrt{n}$ doesn't suit my purpose, maybe adding certain constraint on $Q$ can achieve a smaller upper bound
– tony
Commented Jun 8 at 17:26