Let $\mathbf{a}_k\in\mathbb{C}^n$ for $k=1,2,\ldots,m$ be i.i.d. standard complex normal random vectors with distribution $c\mathcal{N}(0,\mathbf{I})$. I am interested in a tight upper bound on the following quantities with high probabilities (say with probability at least $1-\frac{1}{n}$ or something similar): \begin{align} \underset{\mathbf{x}\in \mathbb{C}^ns.t.\|\mathbf{x}\|_{\ell_2}=1}{\text{max}}\frac{1}{m}\sum_{k=1}^m |\mathbf{a}_k^*\mathbf{x}|^4\le ? \end{align} \begin{align} \underset{\mathbf{x},\mathbf{y}\in \mathbb{C}^ns.t.\|\mathbf{x}\|_{\ell_2}=\|\mathbf{y}\|_{\ell_2}=1} {\text{max}}\frac{1}{m}\sum_{k=1}^m |\mathbf{a}_k^*\mathbf{x}|^2Re(\mathbf{y}^*\mathbf{a}_k\mathbf{a}_k^*\mathbf{x})\le? \end{align}

Of course I know how to do this for fixed quantities of $\mathbf{x}$ and $\mathbf{y}$. However, the corresponding probabilities do not allow for a covering argument. I am hoping that the upper bound for all $\mathbf{x},\mathbf{y}$ is comparable to the result for fixed $\mathbf{x},\mathbf{y}$ up to constant/log factors. If anybody knows of a counter argument which shows that this is not the case that would also be very helpful. Assume that $m \ge c n$ for a sufficiently large numerical constant $c$. I would also be ok with an argument which assumes $m \ge c n (\log n)^\alpha$ for some small $\alpha$ like $\alpha=1,2,3,4$ (the smaller of course the better).

  • $\begingroup$ Whether your hope is true or not, certainly depends on the relation between $m$ and $n$. Let's take two extremes: 1) $m=1$. Then the discrepancy factor is like $n^2$. 2) $m=\infty$. Then the law of large numbers tells you that your quantity is essentially the same for all $x$. $\endgroup$
    – fedja
    May 22 '14 at 17:57
  • $\begingroup$ Thanks! I forgot to mention the relationship between m and n. I have added this in the above $\endgroup$
    – mohi
    May 22 '14 at 18:05

I actually found a simple counter example. Setting $x=\frac{\mathbf{a}_1}{\|\mathbf{a}_1\|_{\ell_2}}$ already rules out my claim.


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.