Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries

Question

Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity matrix. Form a random vector $x'$ in $\mathbb R^m$ as follows.

For $k$ from $1$ through $m$, do the following

• Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.
• Independently of anything else, sample $t$ from $U([0, 1])$.
• Set the $k$th component of $x'$ to $tx_i + (1-t)x_j$.

Let $\Sigma'$ be the covariance matrix of $x'$.

Question. What is a good upper-bound for $\lambda_{\max}(\Sigma')$ ?

My wild guess would be something like $c$ (upto absolute constants).

Answer 1

Here we bound the entire spectrum of $\Sigma'$, from below and above. This post is inspired by a comment of user @BrendanMcKay.

Claim. $\lambda_\max(\Sigma') = O(m/n)$ and $\lambda_\min(\Sigma') = \Omega(n/m)$.

Proof. As remarked by user @BrendanMcKay, $\Sigma' = D + E$, where $D$ is an $m \times m$ diagonal matrix with $D_k = 1/4$ for all $k \in [m]$ and $E$ is an $m \times m$ psd matrix with entries of order $O(1/n)$.

Upper-bound. Since $\Sigma'$ is symmetric, one has

\begin{eqnarray} \begin{split} \lambda_\max(\Sigma') = \|\Sigma'\|_{op} &\le \sqrt{\|\Sigma'\|_1\|\Sigma'\|_\infty} = \|\Sigma'\|_\infty\\ & = \max_{1 \le k \le m}\sum_{1 \le \ell \le m}|\mathbb E\,x'_k x'_\ell|\\ & = \max_{1 \le k \le m}\sum_{1 \le \ell \le m}\begin{cases}1/4,&\mbox{ if }k = \ell,\\ O(1/n),&\mbox{ else} \end{cases}\\ &= O(m/n). \end{split} \end{eqnarray}

Lower-bound. By woodbury identity, $(\Sigma')^{-1} = (D+E)^{-1} = D^{-1}-D^{-1}(I+ED^{-1})^{-1} E D^{-1}$, and so \begin{eqnarray} \begin{split} \|(\Sigma')^{-1}\|_{op} &= \|(D+E)^{-1}\|_{op} = \|D^{-1}\|_{op}+\|D^{-1}\|_{op}\|(I+ED^{-1})^{-1}\|_{op}\|E\|_{op}\|D^{-1}\|_{op}\\ &= \frac{1}{4}+\frac{\|E\|_{op}}{16}\|(I+ED^{-1})^{-1}\|_{op} \le \frac{1}{4} + \frac{\|E\|_{op}}{16} = O(\|E\|_{op}). \end{split} \end{eqnarray} Now, using the same argument as for the first part of the proof, it is easy to obtain $\|E\|_{op} = O(m/n)$. We deduce from the above computations that $\|(\Sigma')^{-1}\|_{op} = O(m/n)$, and so \begin{eqnarray} \lambda_\min(\Sigma') = \frac{1}{\|(\Sigma')^{-1}\|_{op}} = \frac{1}{O(m/n)} = \Omega(n/m). \end{eqnarray}