Dense sample covariance concentration for sub-Gaussian vectors

If $L=0$, [F2] and [F6] imply $P(\mathrm{\parallel }{Z}_i{\mathrm{\parallel }}_2\ge 1\mathrm{/}m)=0$ for each $i$ and positive integer $m$. By [F8], the countable union over $i,m$ shows that every $Z_i=0$ almost surely; then [F9] gives $\mathrm{\Sigma }=0$, and both estimators are exact. Assume $L>0$. Fix a unit vector $u$ and set $W_i=(u^{\mathsf{T}}{Z}_i{)}^2-E[(u^{\mathsf{T}}{Z}_i{)}^2]$. By [F2]–[F3], each $W_i$ is centered sub-exponential with parameters $(256L^2,16L)$; [F10] gives that these variables are iid across $i$.

By [F10] the sample vectors are independent, and [F7] gives, for every $u\in {\mathbb{R}}^p$ and $\lambda \in \mathbb{R}$, $E{e}^{\lambda ⟨u,\bar{Z}⟩}={\prod }_{i=1}^{n}E{e}^{(\lambda \mathrm{/}n)⟨u,Z_i⟩}\le e^{L{\lambda }^2\mathrm{\parallel }u{\mathrm{\parallel }}_2^2\mathrm{/}(2n)}\mathrm{.}$ Thus $\bar{Z}$ is centered sub-Gaussian with proxy $L\mathrm{/}n$. Applying the vector clause of [F6] with a $1\mathrm{/}2$-net at $s=4\sqrt{Lr}$ gives $P(\mathrm{\parallel }\bar{Z}{\mathrm{\parallel }}_2^2>16Lr)\le 2\cdot 5^p{e}^{-2(p+x)}\le \delta \mathrm{/}2,$ since $r=(p+x)\mathrm{/}n$ and $x=\log (4\mathrm{/}\delta )$.

Applying [F4] to ${\sum }_i{W}_i$ gives, for every $t>0$, $P(\mid u^{\mathsf{T}}({\widehat{\mathrm{\Sigma }}}_0-\mathrm{\Sigma })u\mid >t)\le 2\exp [-\frac{1}{2}\min \{\frac{n{t}^2}{256L^2},\frac{nt}{16L}\}]\mathrm{.}$ This is uniform over unit $u$.

Take a $1\mathrm{/}4$-net with at most $9^p$ points and put $x=\log (4\mathrm{/}\delta )$, so $r=(p+x)\mathrm{/}n$. With $C_0=80$ and $t=C_{0}L(\sqrt{r}+r)$, the exponent in step 2.1 is at least $\frac{1}{2}\min \{{80}^2\mathrm{/}256,80\mathrm{/}16\}(p+x)=\frac{5}{2}(p+x)\ge p\log 9+x$. A union bound gives probability at least $1-\delta \mathrm{/}2$ that every net quadratic form is at most $t$ in absolute value.

By [F9], ${\widehat{\mathrm{\Sigma }}}_0-\mathrm{\Sigma }$ is symmetric. On the event in step 3.1, [F5] gives $\mathrm{\parallel }{\widehat{\mathrm{\Sigma }}}_0-\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2t=160L(\sqrt{r}+r)$. This proves the first estimate.

Expanding [F1] gives ${\widehat{\mathrm{\Sigma }}}^{\ast }={\widehat{\mathrm{\Sigma }}}_0-\bar{Z}{\bar{Z}}^{\mathsf{T}}$. For $w\mathrm{\ne }0$ and unit $v$, [F12] gives $\mathrm{\parallel }w{w}^{\mathsf{T}}v{\mathrm{\parallel }}_2=\mathrm{\parallel }w{\mathrm{\parallel }}_2\mathrm{\mid }⟨w,v⟩\mathrm{\mid }\le \mathrm{\parallel }w{\mathrm{\parallel }}_2^2$, with equality at $v=w\mathrm{/}\mathrm{\parallel }w{\mathrm{\parallel }}_2$; if $w=0$, both sides vanish. Thus [F11] gives $\mathrm{\parallel }\bar{Z}{\bar{Z}}^{\mathsf{T}}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=\mathrm{\parallel }\bar{Z}{\mathrm{\parallel }}_2^2$. For vectors $a,b$, [F12] and $\mathrm{\parallel }a+b{\mathrm{\parallel }}_2^2=\mathrm{\parallel }a{\mathrm{\parallel }}_2^2+2⟨a,b⟩+\mathrm{\parallel }b{\mathrm{\parallel }}_2^2$ give $\mathrm{\parallel }a+b{\mathrm{\parallel }}_2\le \mathrm{\parallel }a{\mathrm{\parallel }}_2+\mathrm{\parallel }b{\mathrm{\parallel }}_2$; applying this inside the maximum in [F11] gives $\mathrm{\parallel }A+B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}+\mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Combining the probability-$1-\delta \mathrm{/}2$ events from steps 1.2 and 3.1, their intersection has probability at least $1-\delta$ by [F8], and the resulting error is at most $160L(\sqrt{r}+r)+16Lr\le 176L(\sqrt{r}+r)$.