Clean Gaussian covariance has a capped squared operator lower rate

First suppose $p\ge 16$. Put $N_0=p(p-1)\mathrm{/}2$ and let $W$ range over symmetric sign matrices with zero diagonal and independent $\{-1,1\}$ entries above the diagonal. For fixed unit $v$, $v^{T}Wv=2{\sum }_{i<j}{W}_{ij}{v}_i{v}_j$. For $t\ge 0$, put $h(t)=t-\tanh t$ and $g(t)=t^2\mathrm{/}2-\log (\cosh t)$. By [F9], $h(0)=0$ and $h^{\mathrm{\prime }}(t)=1-{\mathrm{sech}}^{2}t={\tanh }^{2}t\ge 0$, so the mean value theorem gives $h(t)\ge 0$; then $g(0)=0$ and $g^{\mathrm{\prime }}(t)=h(t)\ge 0$. Evenness gives $g(t)\ge 0$ for all real $t$, so $\cosh t\le e^{t^2\mathrm{/}2}$. Since each $W_{ij}$ is a uniform sign and the signs are independent, $\mathbb{E}{e}^{\lambda v^{T}Wv}={\prod }_{i<j}\mathbb{E}{e}^{2\lambda v_i{v}_j{W}_{ij}}={\prod }_{i<j}\cosh (2\lambda v_i{v}_j)\le \exp \text{\hspace{0.17em}⁣}\left(2{\lambda }^2{\sum }_{i<j}{v}_i^2{v}_j^2\right)\le e^{{\lambda }^2}\mathrm{.}$ Chernoff's inequality applied to both signs gives $\mathrm{Pr}(\mathrm{\mid }{v}^{T}Wv\mathrm{\mid }>t)\le 2e^{-t^2\mathrm{/}4}$. By [F2], use a $1\mathrm{/}4$-net with at most $9^p$ points; approximating each unit vector changes its quadratic form by at most $\frac{1}{2}\mathrm{\parallel }W{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Thus $\mathrm{\parallel }W{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2{\max }_{v\text{ in net}}\mathrm{\mid }{v}^{T}Wv\mathrm{\mid }$. A union bound at $t=8\sqrt{p}$ gives failure probability at most $2\cdot 9^p{e}^{-16p}<1\mathrm{/}2$. At least half of the sign matrices therefore satisfy $\mathrm{\parallel }W{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 16\sqrt{p}$.

In the finite Hamming cube of upper-triangular signs, greedily retain a good matrix and delete all good matrices within Hamming distance $\lfloor N_0\mathrm{/}8\rfloor$. Each deleted ball contains at most ${\sum }_{j\le N_0\mathrm{/}8}\left(\genfrac{}{}{0px}{}{N_0}{j}\right)\le e^{N_{0}h(1\mathrm{/}8)}$ words, where $h(t)=-t\log t-(1-t)\log (1-t)$. For $\alpha =1\mathrm{/}8$, the binomial theorem gives $1={\sum }_{j=0}^{N_0}\left(\genfrac{}{}{0px}{}{N_0}{j}\right){\alpha }^j(1-\alpha {)}^{N_0-j}$. Each weight with $j\le \alpha N_0$ is at least ${\alpha }^{\alpha N_0}(1-\alpha {)}^{(1-\alpha )N_0}=e^{-N_{0}h(\alpha )}$, which proves the ball bound. Greedy deletion retains at least $2^{N_0-1}{e}^{-N_{0}h(1\mathrm{/}8)}$ words. The resulting code $\mathcal{W}$ has pairwise Hamming distance greater than $N_0\mathrm{/}8$ and $\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge N_0(\log 2-h(1\mathrm{/}8))-\log 2\ge \frac{1}{20}{p}^2\mathrm{.}$ Here $h(1\mathrm{/}8)<\frac{19}{50}$, $N_0\ge p^2\mathrm{/}3$, and $p\ge 16$. For distinct code matrices, $\mathrm{\parallel }W-W^{\mathrm{\prime }}{\mathrm{\parallel }}_F^2$ is eight times their upper-triangular Hamming distance, hence at least $N_0$.

Now suppose $1\le p\le 15$. Set ${\mathrm{\Sigma }}_0=(M\mathrm{/}2)I$ and ${\mathrm{\Sigma }}_1=(M\mathrm{/}2)I+h{e}_1{e}_1^T$, where $h=\gamma M\sqrt{p\mathrm{/}n}$. The condition $p\mathrm{/}n\le c_1$ and small $\gamma$ make both matrices members of ${\mathcal{F}}_p(M)$. With $t=2h\mathrm{/}M\le 1\mathrm{/}2$, [F3] gives $D(N_p(0,{\mathrm{\Sigma }}_0)\mathrm{\parallel }{N}_p(0,{\mathrm{\Sigma }}_1))=\frac{1}{2}[\log (1+t)+(1+t{)}^{-1}-1]\le t^2\mathrm{/}4.$ The derivative of the bracket is $t\mathrm{/}(1+t{)}^2\le t$, proving the bound. By [F4], the $n$-sample KL is at most ${\gamma }^{2}p\le 15{\gamma }^2$; choose $\gamma$ so it is at most $1\mathrm{/}2$.

Set ${\mathrm{\Sigma }}_W=(M\mathrm{/}2)I+(a\mathrm{/}\sqrt{p})W$ with $a=\gamma M\sqrt{p\mathrm{/}n}$, where $\gamma >0$ is sufficiently small. Since $\mathrm{\parallel }W{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 16\sqrt{p}$, the perturbation has norm at most $16a$; choose $\gamma \sqrt{c_1}\le 1\mathrm{/}64$ so $16a\le M\mathrm{/}4$. Thus each ${\mathrm{\Sigma }}_W$ is positive definite and belongs to ${\mathcal{F}}_p(M)$ by [F1]. If $W\mathrm{\ne }{W}^{\mathrm{\prime }}$, [F8] gives $\mathrm{\parallel }{\mathrm{\Sigma }}_W-{\mathrm{\Sigma }}_{W^{\mathrm{\prime }}}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\ge \frac{a}{p}\mathrm{\parallel }W-W^{\mathrm{\prime }}{\mathrm{\parallel }}_F\ge a\sqrt{\frac{N_0}{p^2}}\ge \frac{a}{2}\mathrm{.}$

Pinsker [F6] gives $\mathrm{\parallel }{P}_0^{\otimes n}-P_1^{\otimes n}{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}\le 1\mathrm{/}2$. By [F7], every binary test has maximum error probability at least $1\mathrm{/}16$. The nearest-covariance test from an arbitrary estimator is wrong only when its operator error is at least $h\mathrm{/}2$; its two decision cells are Borel by finite distance comparisons, so [F10] makes it an admissible test kernel. Therefore one of the two laws has probability at least $1\mathrm{/}16$ of squared error at least $h^2\mathrm{/}4={\gamma }^2{M}^{2}p\mathrm{/}(4n)$. This proves the rate for $p\le 15$.

Let $Q_0=N_p(0,(M\mathrm{/}2)I)$ be a reference law. For each $W$, the relative perturbation has eigenvalues $r_i$ with $\mathrm{\mid }{r}_i\mathrm{\mid }\le 1\mathrm{/}2$ and ${\sum }_i{r}_i=0$. By [F3], $D(N_p(0,{\mathrm{\Sigma }}_W)\mathrm{\parallel }{Q}_0)=\frac{1}{2}{\sum }_i(r_i-\log (1+r_i))\le \frac{1}{2}{\sum }_i{r}_i^2\le 2(a\mathrm{/}M{)}^{2}p\mathrm{.}$ The scalar inequality follows by integrating $t\mathrm{/}(1+t)$ from zero to $r_i$ and using $\mathrm{\mid }t\mathrm{/}(1+t)\mathrm{\mid }\le 2\mathrm{\mid }t\mathrm{\mid }$ for $\mathrm{\mid }t\mathrm{\mid }\le 1\mathrm{/}2$. Also ${\sum }_i{r}_i^2=4a^2\mathrm{\parallel }W{\mathrm{\parallel }}_F^2\mathrm{/}(M^{2}p)$ and $\mathrm{\parallel }W{\mathrm{\parallel }}_F^2=2N_0$. By [F4], the average $n$-sample KL to $Q_0^{\otimes n}$ is at most $2{\gamma }^2{p}^2$. Choose $\gamma$ smaller if needed so this is at most $\frac{1}{10}\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }$.

The Fano factor in [F5] satisfies $1-\frac{1}{10}-\frac{\log 2}{\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }}>\frac{1}{2},$ using $\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge p^2\mathrm{/}20$ and $p\ge 16$. Thus every classifier of the uniform index has error probability greater than $1\mathrm{/}8$. Classify an estimator by its nearest ${\mathrm{\Sigma }}_W$, resolving ties by least index. This rule is Borel: its decision cell for index $j$ is the finite intersection of strict distance comparisons against earlier indices and weak comparisons against later indices. If it is wrong, the triangle inequality and step 2.1 force operator error at least $a\mathrm{/}4$. Thus the supremum tail probability at threshold $a^2\mathrm{/}16$ is greater than $1\mathrm{/}8$. Since $a^2={\gamma }^2{M}^{2}p\mathrm{/}n$, this proves the rate for $p\ge 16$.

Choose $c_1\le 1\mathrm{/}16$ and $c_M\le {\gamma }^2{M}^2\mathrm{/}16$. Steps 4.1 and 2.2 give a probability lower bound at least $c_1$ at threshold $c_{M}p\mathrm{/}n$ in their respective dimension ranges. Taking the infimum over estimators and combining the ranges proves the first, small-ratio assertion for all dimensions satisfying its premise.

Abbreviate the constants just established by $b=c_M>0$ and $c=c_1\in (0,1\mathrm{/}16]$, and put $a_M=\min \{bc\mathrm{/}2,M^{2}c\mathrm{/}64\}$. If $p\mathrm{/}n\le c$, step 5.1 gives tail probability at least $c$ at threshold $bp\mathrm{/}n$. Since $a_M\le b$ and $\min \{1,p\mathrm{/}n\}\le p\mathrm{/}n$, lowering the threshold gives the asserted capped bound in this case.

Suppose $p\mathrm{/}n>c$ and $n\ge 2\mathrm{/}c$. Put $k=\lfloor cn\rfloor$, so $1\le k\le p$ and $c\mathrm{/}2\le k\mathrm{/}n\le c$. Let $J:{\mathbb{R}}^k\to {\mathbb{R}}^p$ be the zero-padding coordinate isometry. For any Borel ambient matrix estimator $A$, the rule $A_k(y_1,\dots ,y_n)=J^{T}A(J{y}_1,\dots ,J{y}_n)J$ is Borel by [F11]. For any matrix $B$, including a nonsymmetric one, $\mathrm{\parallel }{J}^{T}BJ{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$: for each unit $u$, $\mathrm{\parallel }{J}^{T}BJu{\mathrm{\parallel }}_2\le \mathrm{\parallel }BJu{\mathrm{\parallel }}_2\le \mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$ because $J$ is an isometry and $J^T$ discards coordinates. Every $\mathrm{\Theta }\in {\mathcal{F}}_k(M)$ embeds as $J\mathrm{\Theta }{J}^T\in {\mathcal{F}}_p(M)$ by [F1], and [F11] identifies its iid sample with zero-padded $N_k(0,\mathrm{\Theta })$ observations. Apply the small-ratio result of step 5.1 in dimension $k$ to $A_k$. Since $\mathrm{\parallel }{A}_k-\mathrm{\Theta }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\parallel }A-J\mathrm{\Theta }{J}^T{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$, the ambient supremum tail probability is at least $c$ at threshold $bk\mathrm{/}n\ge bc\mathrm{/}2\ge a_M\min \{1,p\mathrm{/}n\}$. This holds for every ambient Borel estimator.

Suppose $p\mathrm{/}n>c$ and $n<2\mathrm{/}c$. Take ${\mathrm{\Sigma }}_0=(M\mathrm{/}2)I_p$ and ${\mathrm{\Sigma }}_1={\mathrm{\Sigma }}_0+h{e}_1{e}_1^T$, where $h=M\sqrt{c}\mathrm{/}4$. Both are positive definite in ${\mathcal{F}}_p(M)$ and their operator separation is $h$. Put $t=2h\mathrm{/}M=\sqrt{c}\mathrm{/}2$. The scalar KL calculation from step 1.3 and [F3] gives $D(P_0\mathrm{\parallel }{P}_1)=\frac{1}{2}[\log (1+t)+(1+t{)}^{-1}-1]\le t^2\mathrm{/}4=h^2\mathrm{/}{M}^2$; the bracket has derivative $t\mathrm{/}(1+t{)}^2\le t$ for $t\ge 0$. Thus [F4] gives $D(P_0^{\otimes n}\mathrm{\parallel }{P}_1^{\otimes n})\le n{h}^2\mathrm{/}{M}^2<1\mathrm{/}8$, and [F6] gives total variation at most $1\mathrm{/}4$. Classify an arbitrary Borel estimator by the nearer of these two covariance matrices, resolving ties by the first index. This is a Borel binary test by [F10]. Apply the expected squared-risk theorem [F7] to that test with scalar targets $0,1$: its squared risks are exactly its error probabilities, so their maximum is at least $(1-\mathrm{T}\mathrm{V})\mathrm{/}8\ge 3\mathrm{/}32\ge c$. A wrong classification forces the original operator error to be at least $h\mathrm{/}2$ by the triangle inequality. The ambient maximum tail probability is therefore at least $c$ at squared threshold $h^2\mathrm{/}4=M^{2}c\mathrm{/}64\ge a_M\min \{1,p\mathrm{/}n\}$.

The three cases in steps 6.1, 7.1, and 7.2 cover every $p,n\ge 1$. Each establishes the same probability constant $c=c_1$ at threshold $a_M\min \{1,p\mathrm{/}n\}$ for every Borel matrix-valued estimator, so taking their infimum proves the all-regime assertion. The preceding small-ratio result remains unchanged.