I'm interested in concentration of the following random matrix sum in spectral norm

$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*$

Here $\mathbf{a}_k\in\mathbb{R}^n$ are i.i.d. standard normal Gaussian vectors distributed as $\mathcal{N}(0,\mathbf{I}_n)$ and $b_k$ are standard normal random variables distributed as $\mathcal{N}(0,1)$ and independent of the $\mathbf{a}_k$'s. I'm interested in showing

I'm interested in showing

$\|\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*-\mathbf{I}\|\le \delta$

holds with high probability as long as $m\ge c(\delta) n$ with $c(\delta)$ a constant depending only on $\delta$. Here for a matrix $\mathbf{X}$ the spectral norm is given by $\|\mathbf{X}\|$. I can get a looser result as long as $m\ge c \frac{n\log n}{\delta^2}$. However, I would like to get rid of the extra log factor. I should also say that for the lower tail I can also get rid of the log factor i.e. prove

$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*\succeq(1-\delta)\mathbf{I}$

holds with high probability as long as $m\ge c \frac{n}{\delta^2}$. So really need only the upper tail. Any proof that getting rid of the extra log for the upper tail is not possible would also be welcome.

  • $\begingroup$ May you kindly comment how to avoid the log factor for the lower bound? $\endgroup$
    – John
    Commented May 12, 2023 at 12:43

1 Answer 1


Removing the log factor for the upper bound is not possible actually.

$\frac{1}{m}\sum_{k=1}^m b_k^2(\mathbf{a}_k^*u)^2\ge \underset{k}{\max}b_k^2\|\mathbf{a}_k\|_{\ell_2}^2\gtrsim \frac{n(\log n)}{m}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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