Clean block-sparse Gaussian covariance has squared operator lower rate s log(ep/s) over n

Suppose $s=1$ and $p\ge 3$. For $1\le j\le p$, let ${\mathrm{\Sigma }}_j=(M\mathrm{/}2)I+h{e}_j{e}_j^T$, where $h=\gamma M\sqrt{\log p\mathrm{/}n}$. These matrices are diagonal, so [F1] places them in ${\mathcal{F}}_{p,1}(M)$. Since $\log p\mathrm{/}n\le c_1$, choose $\gamma \sqrt{c_1}\le 1\mathrm{/}2$ so their largest eigenvalue is at most $M$. Their pairwise operator distance is $h$. Relative to $Q_0=N_p(0,(M\mathrm{/}2)I)$, [F2] and $t=2h\mathrm{/}M\le 1$ give $D(N_p(0,{\mathrm{\Sigma }}_j)\mathrm{\parallel }{Q}_0)=\frac{1}{2}[t-\log (1+t)]\le t^2\mathrm{/}4.$ The inequality follows by integrating $x\mathrm{/}(1+x)\le x$ from $0$ to $t$. By [F3], each $n$-sample KL is at most ${\gamma }^2\log p$.

The remaining case with $s=1$ is $p=2$. Let ${\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{\log (2e)\mathrm{/}n}$. The sample-size condition and small $\gamma$ make both matrices members of ${\mathcal{F}}_{2,1}(M)$. With $t=2h\mathrm{/}M\le 1\mathrm{/}2$, [F2] gives $D(N_2(0,{\mathrm{\Sigma }}_0)\mathrm{\parallel }{N}_2(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 inequality. By [F3], choose $\gamma$ small enough that the $n$-sample KL is at most $1\mathrm{/}2$. Pinsker [F5] gives total variation at most $1\mathrm{/}2$; [F6] then gives maximum binary testing error at least $1\mathrm{/}16$. A wrong nearest covariance decision forces error at least $h\mathrm{/}2$, and its decision cells are Borel by finite distance comparisons, so [F7] gives an admissible test kernel. Thus one law has probability at least $1\mathrm{/}16$ of squared error at least $h^2\mathrm{/}4={\gamma }^2{M}^2\log (2e)\mathrm{/}(4n)$, which is the required rate.

Suppose $s\ge 2$, and put $k=s-1$ and $m=\lfloor (p-1)\mathrm{/}k\rfloor$. Since $p\ge 2s$, $m\ge 2$. Partition $km$ of the $p-1$ coordinates other than coordinate $1$ into $k$ disjoint groups of size $m$. For each word $\omega \in [m{]}^k$, select its indexed coordinate in every group and form the unit vector $v_{\omega }\in {\mathbb{R}}^p$ with value $k^{-1\mathrm{/}2}$ on those $k$ coordinates and zero elsewhere. There are $m^k$ words. Greedily retain a word and delete its Hamming ball of radius $\lfloor k\mathrm{/}100\rfloor$. Each ball has at most ${\sum }_{j\le k\mathrm{/}100}\left(\genfrac{}{}{0px}{}{k}{j}\right)(m-1{)}^j\le \exp \text{\hspace{0.17em}⁣}(kh(1\mathrm{/}100)+(k\mathrm{/}100)\log m)$ words. To obtain the binomial sum bound, put $\alpha =1\mathrm{/}100$; in $1={\sum }_{j=0}^k\left(\genfrac{}{}{0px}{}{k}{j}\right){\alpha }^j(1-\alpha {)}^{k-j}$, each weight for $j\le \alpha k$ is at least $e^{-kh(\alpha )}$, and $(m-1{)}^j\le m^{\alpha k}$.

Use the $p$ diagonal matrices from step 1.1 as the packing and $Q_0^{\otimes n}$ as reference. Choose $\gamma$ so their average KL is at most $\frac{1}{10}\log p$. The Fano factor $1-\frac{1}{10}-\log 2\mathrm{/}\log p>1\mathrm{/}4$ for $p\ge 3$, so [F4] gives classification error greater than $1\mathrm{/}16$. Classify an estimator by its nearest covariance, resolving ties by least index. This rule is Borel because its decision cells are finite intersections of strict or weak comparisons of continuous distances, and [F7] turns it into a deterministic test kernel. If it is misclassified, the triangle inequality forces operator error at least $h\mathrm{/}2$. Thus the supremum tail probability is greater than $1\mathrm{/}16$ at threshold $h^2\mathrm{/}4$. Because $\log (ep)=1+\log p\le 2\log p$, $h^2\mathrm{/}4\ge {\gamma }^2{M}^2\log (ep)\mathrm{/}(8n)$, giving the required rate after reducing $c_M$ if needed.

The retained code $\mathcal{W}$ has pairwise Hamming distance greater than $k\mathrm{/}100$ and $\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge k[(99\mathrm{/}100)\log m-h(1\mathrm{/}100)]\ge \frac{9}{10}k\log m\ge \frac{9}{80}s\log (ep\mathrm{/}s)\mathrm{.}$ Here $h(1\mathrm{/}100)<\frac{3}{50}$ and $\log m\ge \log 2>\frac{69}{100}$. Also $m\ge p\mathrm{/}(2s)$ because $(p-1)\mathrm{/}(s-1)\ge p\mathrm{/}s$ and $\lfloor x\rfloor \ge x\mathrm{/}2$ for $x\ge 2$. Thus $\log (ep\mathrm{/}s)=1+\log (p\mathrm{/}s)\le 1+\log 2+\log m\le 4\log m$, and $k\ge s\mathrm{/}2$. Further $\mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge 3$: if $k=1$, then $m\ge 3$ and no word is removed by a radius-zero ball; if $k\ge 2$, the displayed bound gives $\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge \frac{9}{5}\log 2>\log 3$. Distinct code vectors satisfy $\mathrm{\parallel }{v}_{\omega }-v_{{\omega }^{\mathrm{\prime }}}{\mathrm{\parallel }}_2^2=2d_H(\omega ,{\omega }^{\mathrm{\prime }})\mathrm{/}k>1\mathrm{/}50$.

Define ${\mathrm{\Sigma }}_{\omega }=(M\mathrm{/}2)I+a(e_1{v}_{\omega }^T+v_{\omega }{e}_1^T)$, where $a=\gamma M\sqrt{s\log (ep\mathrm{/}s)\mathrm{/}n}$. The off-diagonal entries lie in the block formed by coordinate $1$ and the $k=s-1$ selected coordinates, so ${\mathrm{\Sigma }}_{\omega }\in {\mathcal{F}}_{p,s}(M)$ by [F1]. The perturbation has eigenvalues $a,-a$ on $\mathrm{span}\{e_1,v_{\omega }\}$ and zero on its orthogonal complement. Choose $\gamma \sqrt{c_1}\le 1\mathrm{/}4$, so $a\le M\mathrm{/}4$; then every ${\mathrm{\Sigma }}_{\omega }$ is positive definite and has top eigenvalue at most $M$. For distinct codewords, $\mathrm{\parallel }{\mathrm{\Sigma }}_{\omega }-{\mathrm{\Sigma }}_{{\omega }^{\mathrm{\prime }}}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=a\mathrm{\parallel }{v}_{\omega }-v_{{\omega }^{\mathrm{\prime }}}{\mathrm{\parallel }}_2>a\mathrm{/}8.$

Let $Q_0=N_p(0,(M\mathrm{/}2)I)$. The relative perturbation has eigenvalues $2a\mathrm{/}M,-2a\mathrm{/}M$ and zero otherwise. By [F2], $D(N_p(0,{\mathrm{\Sigma }}_{\omega })\mathrm{\parallel }{Q}_0)=-\frac{1}{2}\log (1-(2a\mathrm{/}M{)}^2)\le 4(a\mathrm{/}M{)}^2\mathrm{.}$ The scalar inequality follows by integrating $(1-x{)}^{-1}\le 2$ from $0$ to $x=(2a\mathrm{/}M{)}^2\le 1\mathrm{/}2$. By [F3], the $n$-sample KL to $Q_0^{\otimes n}$ is at most $4{\gamma }^{2}s\log (ep\mathrm{/}s)$. Since $\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }\ge \frac{9}{10}s\log (ep\mathrm{/}s)\mathrm{/}8$, choose ${\gamma }^2\le \frac{9}{3200}$ so this KL is at most $\frac{1}{10}\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }$.

The Fano factor obeys $1-\frac{1}{10}-\frac{\log 2}{\log \mathrm{\mid }\mathcal{W}\mathrm{\mid }}\ge 1-\frac{1}{10}-\frac{\log 2}{\log 3}>\frac{1}{4}\mathrm{.}$ Thus [F4] gives every classifier error greater than $1\mathrm{/}16$. Nearest-covariance classification from any estimator is wrong only when its operator error is at least half the separation from step 3.1, hence at least $a\mathrm{/}16$. The finite nearest-code rule is Borel by finite distance comparisons, so [F7] makes it a classifier kernel. The supremum tail probability at threshold $a^2\mathrm{/}256$ is therefore greater than $1\mathrm{/}16$, proving the rate for $s\ge 2$.

Choose $c_1\le 1\mathrm{/}16$ and $c_M\le {\gamma }^2{M}^2\mathrm{/}256$. The bounds from steps 2.1, 1.2, and 5.1 cover the cases $s=1,p\ge 3$, $s=1,p=2$, and $s\ge 2$, respectively, and give probability at least $c_1$ at threshold $c_{M}s\log (ep\mathrm{/}s)\mathrm{/}n$. Taking the infimum over estimators and combining the cases proves the claim.