Oracle-truncated covariance and vector concentration under finite matrix variance

Put $A=Z{Z}^T$ and $A_{\theta }=w(Z)Z{Z}^T$. The weight is a Borel function, including its declared value at zero, so all transformations used here preserve the independence of the samples by [F3]. The rank-one spectral calculus gives $0⪯A_{\theta }⪯RI$ and $A_{\theta }^2⪯A^2$. For a scalar $x\ge 0$, $(x-R{)}_{+}\le x^2\mathrm{/}(4R)$: the inequality is immediate for $x\le R$, and for $x\ge R$ it is equivalent to $(x-2R{)}^2\ge 0$. Applying it to the eigenvalues of $A$ proves $0⪯A-A_{\theta }⪯\theta A^2\mathrm{/}4$. Therefore $0⪯\mathrm{\Sigma }-\mathbb{E}{A}_{\theta }⪯\theta \mathbb{E}{A}^2\mathrm{/}4$ and $\mathrm{\parallel }\mathrm{\Sigma }-\mathbb{E}{A}_{\theta }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \theta {\sigma }_0^2\mathrm{/}4$. Nonzero covariance also implies ${\sigma }_0>0$: a positive variance in some unit direction forces $\mathbb{E}[\mathrm{\parallel }Z{\mathrm{\parallel }}^2⟨Z,v{⟩}^2]\ge \mathbb{E}⟨Z,v{⟩}^4>0$. Thus the displayed thresholds are well-defined.

Put $Y=w(Z)Z$. Its norm is at most $1\mathrm{/}\sqrt{\theta }$: for $\mathrm{\parallel }Z\mathrm{\parallel }\le \sqrt{R}$ use $\mathrm{\parallel }Y\mathrm{\parallel }\le \sqrt{R}$, and otherwise use $\mathrm{\parallel }Y\mathrm{\parallel }=R\mathrm{/}\mathrm{\parallel }Z\mathrm{\parallel }\le \sqrt{R}$. Since $\mathbb{E}Z=0$, $\mathbb{E}Y=-\mathbb{E}[(1-w(Z))Z]$. For a unit vector $v$, apply [F3] to $U=\mathrm{\parallel }Z\mathrm{\parallel }⟨Z,v⟩$ and $W=(1-w(Z))\mathrm{/}\mathrm{\parallel }Z\mathrm{\parallel }$, assigning $W=0$ at zero. Then $\mathbb{E}{U}^2\le {\sigma }_0^2$ by matrix variance, and $W^2\le \theta$ pointwise: it vanishes on $\mathrm{\parallel }Z{\mathrm{\parallel }}^2\le R$, and elsewhere is at most $1\mathrm{/}\mathrm{\parallel }Z{\mathrm{\parallel }}^2\le 1\mathrm{/}R$. Thus $\mathrm{\mid }⟨\mathbb{E}Y,v⟩\mathrm{\mid }\le {\sigma }_0\sqrt{\theta }$. Taking the Euclidean dual supremum proves $\mathrm{\parallel }\mathbb{E}Y\mathrm{\parallel }\le {\sigma }_0\sqrt{\theta }$.

Set $B_i=A_{\theta ,i}-\mathbb{E}{A}_{\theta }$. Since both matrices subtracted lie between $0$ and $RI$, $-RI⪯B_i⪯RI$, whence $\mathrm{\parallel }{B}_i{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le R$. Expanding the square and taking expectations, without any commutativity requirement, gives $\mathbb{E}{B}_i^2=\mathbb{E}{A}_{\theta }^2-(\mathbb{E}{A}_{\theta }{)}^2⪯\mathbb{E}{A}^2$. The left side is positive semidefinite; hence its norm is at most ${\sigma }_0^2$. The matrices $B_i$ are independent and centered.

For a vector $y\in {\mathbb{R}}^p$ define its symmetric dilation $D(y)=\left(\begin{array}{cc}0& y^T\\ y& 0\end{array}\right)$ of size $p+1$. Its square is $\mathrm{diag}(\mathrm{\parallel }y{\mathrm{\parallel }}_2^2,y{y}^T)$; its nonzero eigenvalues when $y\mathrm{\ne }0$ are $\mathrm{\parallel }y{\mathrm{\parallel }}_2$ and $-\mathrm{\parallel }y{\mathrm{\parallel }}_2$, as is checked on the span of $(1,0)$ and $(0,y\mathrm{/}\mathrm{\parallel }y\mathrm{\parallel })$. It vanishes on the orthogonal complement, so ${\lambda }_{\max }(D(y))=\mathrm{\parallel }D(y){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=\mathrm{\parallel }y{\mathrm{\parallel }}_2$, also at zero. For $C_i=D(Y_i-\mathbb{E}Y)$, step 1.2 gives $\mathrm{\parallel }{C}_i\mathrm{\parallel }\le 2\mathrm{/}\sqrt{\theta }$. The square identity gives $\mathbb{E}{C}_i^2=\mathrm{diag}(\mathbb{E}\mathrm{\parallel }Y-\mathbb{E}Y{\mathrm{\parallel }}^2,\mathbb{E}[(Y-\mathbb{E}Y)(Y-\mathbb{E}Y{)}^T])$. Its norm is at most $\mathbb{E}\mathrm{\parallel }Y-\mathbb{E}Y{\mathrm{\parallel }}^2\le \mathbb{E}\mathrm{\parallel }Y{\mathrm{\parallel }}^2\le \mathbb{E}\mathrm{\parallel }Z{\mathrm{\parallel }}^2=T$; for the lower block, test a unit vector and bound its squared scalar projection by the squared norm. The $C_i$ are independent centered symmetric matrices.

Let $b=\beta +\log 2$ and use [F2] with the fixed Chernoff parameter $s=\theta$; it is admissible since $\theta R=1<3$. Its exponent bound is $3m{\theta }^2{\sigma }_0^2\mathrm{/}4$. Consequently, for $u=3m\theta {\sigma }_0^2\mathrm{/}4+b\mathrm{/}\theta$, the one-sided failure is at most $p{e}^{-b}$; apply the same statement to $-B_i$ and take a union to obtain $\mathbb{P}\{\mathrm{\parallel }S-\mathbb{E}{A}_{\theta }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}>3\theta {\sigma }_0^2\mathrm{/}4+b\mathrm{/}(m\theta )\}\le 2p{e}^{-b}=p{e}^{-\beta }$. Adding the bias from step 1.1 and using ${\sigma }_0\le \sigma$ yields $\theta {\sigma }_0^2+b\mathrm{/}(m\theta )\le (2+(\log 2)\mathrm{/}\beta )\sigma \sqrt{t}$. Define $E_S$ by this bound. Finally $\log 2<7\mathrm{/}10$ since the first four nonnegative terms of $e^{7\mathrm{/}10}$ sum to $1+7\mathrm{/}10+49\mathrm{/}200+343\mathrm{/}6000>2$; since $\beta >1$, the claimed strict bound by $27\mathrm{/}10$ follows.

For the alternative radius, apply the two-sided explicit form in [F2] to the same $B_i$, now with confidence parameter $\beta$. After division by $m$ its radius is $\sqrt{2{\sigma }_0^2\beta \mathrm{/}m}+2R\beta \mathrm{/}(3m)$. Adding the bias $\theta {\sigma }_0^2\mathrm{/}4$ and substituting $R=1\mathrm{/}\theta$, $\theta =\sqrt{t}\mathrm{/}\sigma$, and ${\sigma }_0\le \sigma$, gives the displayed radius $(\sqrt{2}+2\mathrm{/}3+1\mathrm{/}4)\sigma \sqrt{t}$ with failure at most $2p{e}^{-\beta }$.

Apply the one-sided explicit Bernstein bound [F2] to $C_i$ with dimension $p+1$, bound $R_0=2\mathrm{/}\sqrt{\theta }$, variance bound $v=T$ and confidence $b=\beta +\log 2$. Since ${\lambda }_{\max }({\sum }_i{C}_i)=\mathrm{\parallel }{\sum }_i(Y_i-\mathbb{E}Y)\mathrm{\parallel }$, division by $m$ gives $\mathrm{\parallel }V-\mathbb{E}Y\mathrm{\parallel }\le \sqrt{2Tb\mathrm{/}m}+4b\mathrm{/}(3m\sqrt{\theta })$ outside probability $(p+1)e^{-b}=(p+1)e^{-\beta }\mathrm{/}2$. Because $\log 2<1<\beta$, one has $b<2\beta$, and the radius is at most $2\sqrt{Tt}+8t\mathrm{/}(3\sqrt{\theta })$. Adding step 1.2 proves the stated vector bound and defines $E_V$. The two events were obtained from the original independent observations without conditioning on any other statistic. Together with steps 3.1 and 3.2 this proves every asserted conclusion.