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.


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, privacy policy and cookie policy

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