1
$\begingroup$

Let $d,m \to \infty$ (integers) with $m/d \to \rho \in (0, \infty)$. Let $C$ be a $d \times d$ psd matrix with $trace(C)=\mathcal O(1)$, and let $w_1,\ldots,w_m$ be iid uniformly distributed on the unit-sphere in $\mathbb R^d$. Consider the quartic form $$ F := \frac{1}{m}\sum_{j,\ell=1}^m (w_j^\top w_\ell)(w_j^\top C w_\ell). $$

Question. What are good probabilistic lower and upper-bounds for $F$ only in terms of $\rho$ and the eigenvalues of $C$ ?

For example, the solution for the case where $C$ is diagonal will already be very helpful.

Isotropic example

Thanks to this post https://mathoverflow.net/a/334219/78539, we know that if $C = (1/d) I_d$, then $F = m^{-1}\|WW^\top\|_F^2 = m^{-1}\sum_{j}\lambda_j(W W^\top)^2\overset{a.s}{\to} \langle \lambda^2\rangle_{\text{MP}(1/\rho)}$ (if I haven't made some scaling errors), where $\text{MP}(\gamma)$ is the Marchenko-Pastur law with parameter $\gamma$.

$\endgroup$
9
  • $\begingroup$ Thanks for the input. Why does knowing $E[w_jw_j^\top]$ allow to compute $\mathbb E[F]$ ? $\endgroup$
    – dohmatob
    Jun 29 at 15:04
  • 1
    $\begingroup$ I deleted my comment as there was a mistake. Use the trace trick, $w_l^Tw_j w_j^TC w_l = trace[w_jw_j^TCw_lw_l^T]$, by indendence of $w_j,w_l$ the expectation of the sum of non-diagonal terms is $m(m-1)/(md^2)trace[C]$. For the diagonal terms, same story with the simplification $w_j^Tw_j=1$. You can verify the answer using $\langle\lambda^2\rangle=mean^2+variance$ where mean/variance of the MP law are known and simple. $\endgroup$
    – jlewk
    Jun 29 at 15:10
  • $\begingroup$ Would Gaussian iid entries be fine, or do you absolutely need uniform vectors on the sphere? In the Gaussian case the second moment of $E[F]-F$ shouldn't be out of reach. $\endgroup$
    – jlewk
    Jun 29 at 15:22
  • $\begingroup$ No, I'm fine with gaussian iid. In fact, any log-concave isotropic distribution on $\mathbb R^d$ such that $\mathbb E[\|w_1\|^2] = 1$. Thanks in advance for estimate of variance of $F$ (which can be used to get concentration, via Chebychev inequality). $\endgroup$
    – dohmatob
    Jun 29 at 15:30
  • $\begingroup$ @jlewk Moments of $F-E[F]$ will presumably be very hard to compute without some clever trick (of which I'm not aware). Thanks in advance for any insights. $\endgroup$
    – dohmatob
    Jun 29 at 15:37
1
$\begingroup$

Assume iid $N(0,1)$ entries, assume $C$ diagonal, and focus first on the non-diagonal terms:

$G=\sum_j \sum_{l\ne j} w_j^Tw_l w_j^TCw_l = \sum_{j\ne l, ik} w_{ji}w_{li} c_i w_{jk} w_{lk}$. Write this quantity as $$ \begin{split} G=\sum_{j\ne l, i\ne k} w_{ji}w_{li} c_i w_{jk} w_{lk} &+ \sum_{j\ne l, i=k} (w_{ij}^2-1)(w_{lj}^2 -1)c_i \\ &+(w_{ij}^2-1)c_i + (w_{lj}^2 -1)c_i +c_i \end{split} $$ This is a decomposition in uncorrelated polynomials (any two terms are uncorrelated), so that the second moment is $$ E[(G-m(m-1)trace[C])^2]=\sum_{j\ne l, i \ne k} c_i^2 + \sum_{j\ne l, i}(E[(Z^2-1)^2]^2 + 2 E[(Z^2-1)^2])c_i^2. $$ $$= m(m-1)\|C\|_F^2((d-1)+E[(Z^2-1)^2]^2 + 2E[(Z^2-1)^2]).$$ The dominant term is of order $m^2d \|C\|_F^2$, while the mean is $m(m-1)trace[C]$. Hence $G/E[G]-1$ converges to 0 in probability (or in L2) provided that $E[G]^2 \gg Var[G]$, that is, $$ m^2 trace[C] \gg \|C\|_F m \sqrt{d}. $$

For the diagonal terms, we have $\sum_j d w_j^TCw_j + \sum_{j} (\|w_j\|^2-d)w_j^TCw_j$. The second term is negligible compared to the first one if you use $\chi^2$ concentration (e..g, Bernstein inequality) for $\|w_j\|^2-d$, while the first term has mean $md trace[C]$ and variance $2md^2\|C\|_F^2$. Again, the mean dominates the standard deviation if and only if $$ m d ~trace[C] \gg \sqrt m d \|C\|_F.$$ This is equivalent to the condition on the non-diagonal terms if $m\asymp d$.

Edit: since $\|C\|_F^2 \le trace[C]^2$ for $C$ psd, these conditions are always satisfied.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.