Gaussian mixture lower bound for weakly sparse covariance

Choose $v^2<(\beta -1)\mathrm{/}(4\beta )$ and put $r=\lfloor p\mathrm{/}2\rfloor$. Write $x=c\mathrm{/}[2(sϵ{)}^q]$, so $x\ge 2$ and $k=\lfloor x\rfloor \ge 2$ and $k\ge x\mathrm{/}2$. The radius condition gives $x\le C\sqrt{n}\mathrm{/}(\log p{)}^{3\mathrm{/}2}$, hence $k^2\le Cn\mathrm{/}(\log p{)}^3$, $kϵ\le C\mathrm{/}\log p$, and $n{ϵ}^4{k}^2\le C\mathrm{/}\log p$. Also $k^2{p}^{2v^2}\mathrm{/}r\le C{p}^{1\mathrm{/}\beta +2v^2-1}\mathrm{/}(\log p{)}^3\to 0$, uniformly over admitted $n,c$. All constants depend only on fixed parameters. Increase $P_0$ so $r\ge 16k$, $2kϵ\le 1\mathrm{/}3$, and the small bounds below hold. Let $\mathrm{\Lambda }$ be all $r\times r$ zero-one matrices with every row sum $k$ and every column sum at most $2k$; cyclic shifts of a $k$-set show it is nonempty. For $\gamma \in \{0,1{\}}^r$, embed $D_{\gamma }\lambda$ as the upper-right block of a symmetric off-diagonal matrix $A(\gamma ,\lambda )$, using two disjoint $r$-coordinate blocks and an extra zero coordinate if $p$ is odd, and put ${\mathrm{\Sigma }}_{\gamma ,\lambda }=s(I_p+ϵA(\gamma ,\lambda ))$. Every absolute row sum of $A$ is at most $2k$. For any $z$, $\mathrm{\mid }{z}^{\mathsf{T}}Az\mathrm{\mid }\le \frac{1}{2}{\sum }_{j,l}\mathrm{\mid }{A}_{jl}\mathrm{\mid }(z_j^2+z_l^2)\le 2k\mathrm{\parallel }z{\mathrm{\parallel }}_2^2$; applying this to unit eigenvectors and using [F4] bounds the eigenvalues of $A$ in $[-2k,2k]$. Thus ${\mathrm{\Sigma }}_{\gamma ,\lambda }$ is positive definite with eigenvalues in $[2s\mathrm{/}3,4s\mathrm{/}3]\subset (0,\tau ]$. Each column has at most $2k$ off-diagonal entries of magnitude $sϵ$. If $0<q<1$, its weak-${\mathrm{\ell }}_q$ quantity is at most $2k(sϵ{)}^q\le c$; if $q=0$, its nonzero count is at most $2k\le c$. Hence [F2] puts every covariance in the radius-$c$ class. The standard-normal density gives $P(\mathrm{\mid }Z\mathrm{\mid }>t)=e^{-t^2\mathrm{/}2}\sqrt{2\mathrm{/}\pi }{\int }_0^{\mathrm{\infty }}{e}^{-w^2\mathrm{/}2-tw}dw\le e^{-t^2\mathrm{/}2}$, so [F1] verifies the directional-tail condition. For any rectangular matrix $M$ and vector $z$, [F5] gives $\mathrm{\mid }(Mz{)}_i{\mathrm{\mid }}^2\le ({\sum }_j\mathrm{\mid }{M}_{ij}\mathrm{\mid })({\sum }_j\mathrm{\mid }{M}_{ij}\mathrm{\mid }{z}_j^2)$. Summing over rows yields $\mathrm{\parallel }Mz{\mathrm{\parallel }}_2^2\le ({\max }_i{\sum }_j\mathrm{\mid }{M}_{ij}\mathrm{\mid })({\max }_j{\sum }_i\mathrm{\mid }{M}_{ij}\mathrm{\mid })\mathrm{\parallel }z{\mathrm{\parallel }}_2^2$, hence $\mathrm{\parallel }M{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2\le ({\max }_i{\sum }_j\mathrm{\mid }{M}_{ij}\mathrm{\mid })({\max }_j{\sum }_i\mathrm{\mid }{M}_{ij}\mathrm{\mid })$. Therefore each cross-block matrix $C=ϵD_{{\gamma }_{-1}}L$ below has $\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \sqrt{2}kϵ\le 2kϵ$.

Give $(\gamma ,\lambda )$ the uniform prior on $\{0,1{\}}^r\times \mathrm{\Lambda }$. Fix bit $i$, say $i=1$ by row symmetry, and condition on the remaining bit vector ${\gamma }_{-1}$ and nuisance rows $L=({\lambda }_2,\dots ,{\lambda }_r)$. The number of possible first-row supports is $N(L)=\left(\genfrac{}{}{0px}{}{d(L)}{k}\right)$, where $d(L)$ counts columns whose nuisance sum is less than $2k$. Since there are $(r-1)k$ nuisance ones, $d(L)\ge r\mathrm{/}2$. The marginal prior of $L$ is $\pi (L)=N(L)\mathrm{/}\mathrm{\mid }\mathrm{\Lambda }\mathrm{\mid }$, independent of ${\gamma }_{-1}$; conditional on $L$, a support $A$ is uniform among its $N(L)$ available $k$-sets. For each fixed ${\gamma }_{-1}$, when ${\gamma }_1=0$ let $Q_{{\gamma }_{-1},L}$ be the Gaussian n-sample law, which does not depend on $A$; when ${\gamma }_1=1$, let $P_{{\gamma }_{-1},A,L}$ be the n-sample law and ${\bar{P}}_{{\gamma }_{-1},L}$ its uniform support mixture. In the chi-square expansion draw two independent available supports $A,B$ given $L$. Their joint mass with $L$ is proportional to $1\mathrm{/}N(L)$, so given $A,B,{\gamma }_{-1}$ the nuisance rows are not asserted uniform.

Fix ${\gamma }_{-1}$ and let $C\in {\mathbb{R}}^{r\times r}$ be the cross-block matrix with first row zero and remaining rows $ϵ{\gamma }_l{\lambda }_l$. Under $Q_{{\gamma }_{-1},L}$, after canceling $s$, the covariance is $B_0=\left(\begin{array}{cc}{I}_r& C\\ C^{\mathsf{T}}& I_r\end{array}\right)$, with an extra identity coordinate if $p$ is odd. Put $R=(I_r-C^{\mathsf{T}}C{)}^{1\mathrm{/}2}$; it is positive definite because $\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}<1$. The block matrix $T=\left(\begin{array}{cc}{I}_r& 0\\ C^{\mathsf{T}}& R\end{array}\right)$ satisfies $T{T}^{\mathsf{T}}=B_0$. Whiten by $T^{-1}$, extended by the identity on any extra coordinate. If $e=e_1$ is the first coordinate in the left block and $v_A={\mathbf{1}}_A$ is the right-block support vector, then $T^{-1}e=e$ and $T^{-1}{v}_A=R^{-1}{v}_A$. Thus the alternative covariances become $I+{\mathrm{\Delta }}_A$ and $I+{\mathrm{\Delta }}_B$, where ${\mathrm{\Delta }}_A=e{u}^{\mathsf{T}}+u{e}^{\mathsf{T}}$, ${\mathrm{\Delta }}_B=e{w}^{\mathsf{T}}+w{e}^{\mathsf{T}}$, $u=ϵR^{-1}{v}_A$, $w=ϵR^{-1}{v}_B$, and $u,w\perp e$. With $H=(I_r-C^{\mathsf{T}}C{)}^{-1}$, $u^{\mathsf{T}}w=t={ϵ}^2{\mathbf{1}}_A^{\mathsf{T}}H{\mathbf{1}}_B$. The operator norms of ${\mathrm{\Delta }}_A,{\mathrm{\Delta }}_B$ equal $\mathrm{\parallel }u{\mathrm{\parallel }}_2,\mathrm{\parallel }w{\mathrm{\parallel }}_2$, respectively. Since $\mathrm{\parallel }{R}^{-1}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le (1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2{)}^{-1\mathrm{/}2}$, these norms are at most $ϵ\sqrt{k}\mathrm{/}\sqrt{1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2}<1\mathrm{/}4$ for large $P_0$; here $ϵ\sqrt{k}=(kϵ)\mathrm{/}\sqrt{k}\le C\mathrm{/}(\sqrt{2}\log p)$. For positive-definite $S$, [F1], [F6] and [F7] give the Lebesgue density $f_S(x)=(2\pi {)}^{-p\mathrm{/}2}(\det S{)}^{-1\mathrm{/}2}\exp (-x^{\mathsf{T}}{S}^{-1}x\mathrm{/}2)$: the independent standard-normal coordinates have product density, and the invertible linear map $S^{1\mathrm{/}2}$ changes variables with determinant $(\det S{)}^{1\mathrm{/}2}$. For the one-observation laws, write $f_A,f_B,f_0$ for the positive densities of the two alternatives and the whitened baseline. Put $M=(I+{\mathrm{\Delta }}_A{)}^{-1}+(I+{\mathrm{\Delta }}_B{)}^{-1}-I$. Each inverse has smallest eigenvalue at least $(1+1\mathrm{/}4{)}^{-1}=4\mathrm{/}5$, hence $M⪰(3\mathrm{/}5)I$. The product density $f_A{f}_B\mathrm{/}{f}_0$ has exponent matrix $M$ and normalizing factor $(2\pi {)}^{-p\mathrm{/}2}[\det (I+{\mathrm{\Delta }}_A)\det (I+{\mathrm{\Delta }}_B){]}^{-1\mathrm{/}2}$. Diagonalizing $M$ by [F4], applying an orthogonal change of variables and scaling each one-dimensional standard-normal density [F6, F7] gives $\int \frac{f_A(x)f_B(x)}{f_0(x)}dx=[\det (I+{\mathrm{\Delta }}_A)\det (I+{\mathrm{\Delta }}_B)\det M{]}^{-1\mathrm{/}2}\mathrm{.}$ The identity $(I+{\mathrm{\Delta }}_A)M(I+{\mathrm{\Delta }}_B)=I-{\mathrm{\Delta }}_A{\mathrm{\Delta }}_B$ and determinant multiplicativity For same-sized finite square matrices over a commutative ring, $\det (AB)=\det (A)\det (B)$ reduce it to $\det (I-{\mathrm{\Delta }}_A{\mathrm{\Delta }}_B{)}^{-1\mathrm{/}2}$. Since $u,w\perp e$, ${\mathrm{\Delta }}_A{\mathrm{\Delta }}_B=te{e}^{\mathsf{T}}+u{w}^{\mathsf{T}}$. On $\mathrm{span}\{e\}$, $I-{\mathrm{\Delta }}_A{\mathrm{\Delta }}_B$ contributes determinant $1-t$. On $e^{\perp }$, if $u=0$ the rank-one determinant is $1$; otherwise choose an orthonormal basis whose first vector is $u\mathrm{/}\mathrm{\parallel }u{\mathrm{\parallel }}_2$, so $I-u{w}^{\mathsf{T}}$ has only its first row changed and determinant $1-w^{\mathsf{T}}u=1-t$. The full determinant is $(1-t{)}^2$, and the one-observation cross integral is $(1-t{)}^{-1}$. The n-sample laws have product densities by the product joint-law supplier in [F6]; repeated Tonelli [F8] therefore makes their cross integral the nth power, $(1-t{)}^{-n}$.

Write $J=\mathrm{\mid }A\cap B\mathrm{\mid }$, $X_l=\mathrm{\mid }A\cap \mathrm{supp}{\lambda }_l\mathrm{\mid }$ and $Y_l=\mathrm{\mid }B\cap \mathrm{supp}{\lambda }_l\mathrm{\mid }$. The identity $H-I=C^{\mathsf{T}}(I-C{C}^{\mathsf{T}}{)}^{-1}C$ follows from $H-I=(I-C^{\mathsf{T}}C{)}^{-1}{C}^{\mathsf{T}}C$ and $(I-C^{\mathsf{T}}C)C^{\mathsf{T}}=C^{\mathsf{T}}(I-C{C}^{\mathsf{T}})$. The Neumann series $(I-C{C}^{\mathsf{T}}{)}^{-1}={\sum }_{m\ge 0}(C{C}^{\mathsf{T}}{)}^m$ converges because $\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}<1$; since $C$ has nonnegative entries, $H-I$ is entrywise nonnegative and $t-J{ϵ}^2\ge 0$. The eigenvalues of $C{C}^{\mathsf{T}}$ lie in $[0,\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2]$, so [F4] gives $\mathrm{\parallel }(I-C{C}^{\mathsf{T}}{)}^{-1}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le (1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2{)}^{-1}$. Also $(C{\mathbf{1}}_A{)}_l=ϵ{\gamma }_l{X}_l$ and $(C{\mathbf{1}}_B{)}_l=ϵ{\gamma }_l{Y}_l$. Cauchy--Schwarz [F5] and $2ab\le a^2+b^2$ yield $0\le t-J{ϵ}^2\le \frac{{ϵ}^4}{2(1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2)}{\sum }_{l=2}^r(X_l^2+Y_l^2)\mathrm{.}$ Since $\mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le (1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2{)}^{-1}$ and $\mathrm{\parallel }{\mathbf{1}}_A{\mathrm{\parallel }}_2=\mathrm{\parallel }{\mathbf{1}}_B{\mathrm{\parallel }}_2=\sqrt{k}$, [F5] also gives $t\le {ϵ}^{2}k\mathrm{/}(1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2)$. Since $k\ge 2$ and $kϵ\le C\mathrm{/}\log p$, ${ϵ}^{2}k=(kϵ{)}^2\mathrm{/}k=o(1)$, so $t=o(1)$. The derivative of $-\log (1-x)$ is at most $2$ for $0\le x\le t\le 1\mathrm{/}2$; since $1-\mathrm{\parallel }C{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2\ge 8\mathrm{/}9$, the preceding bound gives $(1-t{)}^{-n}\le (1-J{ϵ}^2{)}^{-n}\exp \{\theta {\sum }_{l=2}^r(X_l^2+Y_l^2)\},\theta =2n{ϵ}^4\mathrm{.}$

Fix $A,B,{\gamma }_{-1}$ and all nuisance rows except row $l$, and let $a_j$ be the sum in column $j$ over those fixed rows. A support $S$ for row $l$ is feasible exactly when $\mathrm{\mid }S\mathrm{\mid }=k$, $a_j+{\mathbf{1}}_{\{j\in S\}}\le 2k$ for every column, and $a_j+{\mathbf{1}}_{\{j\in S\}}<2k$ for every $j\in A\cup B$ (so both first-row supports remain available). Thus before prior weighting row $l$ is uniform over the $k$-subsets of the fixed set $V=\{j\in A\cup B:a_j\le 2k-2\}\cup \{j\mathrm{\notin }A\cup B:a_j\le 2k-1\}\mathrm{.}$ At most $(r-2)k\mathrm{/}(2k)\le r\mathrm{/}2$ columns outside $A\cup B$ have $a_j=2k$, so deleting these and $A\cup B$ leaves at least $r\mathrm{/}2-2k\ge r\mathrm{/}4$ available columns; hence $d_0=\mathrm{\mid }V\mathrm{\mid }\ge r\mathrm{/}4$. The first-row availability count is $d(L)=\mathrm{\#}\{j:a_j+{\mathbf{1}}_{\{j\in S\}}<2k\}$; as $S$ varies, only columns outside $A\cup B$ with $a_j=2k-1$ can change this count, so its range has width at most $k\le 2k$. Since $d(L)\ge r\mathrm{/}2$ and $\left(\genfrac{}{}{0px}{}{d+1}{k}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{d}{k}\right)=(d+1)\mathrm{/}(d+1-k)$, the ratio of any two weights $1\mathrm{/}N(L)$ is at most $\exp (C{k}^2\mathrm{/}r)\le 2$ after increasing $P_0$. Thus the actual conditional density of the row support is at most twice the uniform-subset density on $V$. If $m=\mathrm{\mid }A\cap V\mathrm{\mid }$, singleton and ordered-pair inclusion probabilities give $E{X}_l=mk\mathrm{/}{d}_0\le C{k}^2\mathrm{/}r$ and $E[X_l(X_l-1)]=m(m-1)k(k-1)\mathrm{/}(d_0(d_0-1))\le C{k}^4\mathrm{/}{r}^2$. Hence $E{X}_l^2\le C(k^2\mathrm{/}r+k^4\mathrm{/}{r}^2)$; the same bound holds for $Y_l$ and under the weighted law with twice the constant. Since $\theta k^2=o(1)$, $e^z-1\le 2z$ for $0\le z\le 1$ yields $E[\exp \{\theta (X_l^2+Y_l^2)\}\mid \text{all other rows},A,B,{\gamma }_{-1}]\le 1+C\theta (k^2\mathrm{/}r+k^4\mathrm{/}{r}^2)\mathrm{.}$

Put $f_l=\exp \{\theta (X_l^2+Y_l^2)\}$ and $B_0=1+C\theta (k^2\mathrm{/}r+k^4\mathrm{/}{r}^2)$. Every factor except $f_l$ is measurable when all rows except $l$ are fixed. Thus for any subset $S$ containing $l$, conditional expectation gives $E[{\prod }_{j\in S}{f}_j\mid A,B,{\gamma }_{-1}]\le B_{0}E[{\prod }_{j\in S\setminus \{l\}}{f}_j\mid A,B,{\gamma }_{-1}]\mathrm{.}$ Iterating over the finitely many nuisance rows yields $E[\exp \{\theta {\sum }_{l=2}^r(X_l^2+Y_l^2)\}\mid A,B,{\gamma }_{-1}]\le B_0^{r-1}\le \exp \{Cn{ϵ}^4(k^2+k^4\mathrm{/}r)\}=1+o(1)$ uniformly in $A,B,{\gamma }_{-1}$. No row independence is used.

Given $L$, $A,B$ are independent uniform $k$-subsets of a set of size $d\ge r\mathrm{/}2$. Expanding $z^J=(1+(z-1){)}^J$ and using $E\left(\genfrac{}{}{0px}{}{J}{j}\right)=\left(\genfrac{}{}{0px}{}{k}{j}\right)\frac{(k{)}_j}{(d{)}_j}\le \frac{[k^2\mathrm{/}(d-k+1){]}^j}{j!}$ gives $E[z^J\mid L]\le \exp \{k^2(z-1)\mathrm{/}(d-k+1)\}$. Since $J\le k$ and ${ϵ}^{2}k=o(1)$, $(1-J{ϵ}^2{)}^{-n}\le \exp (2n{ϵ}^{2}J)=p^{2v^{2}J}$. Define ${\chi }^2({\bar{P}}_{{\gamma }_{-1},L},Q_{{\gamma }_{-1},L})=\int (d{\bar{P}}_{{\gamma }_{-1},L}\mathrm{/}d{Q}_{{\gamma }_{-1},L}-1{)}^{2}d{Q}_{{\gamma }_{-1},L}$. Finite expansion of the mixture density gives $1+{\chi }^2({\bar{P}}_{{\gamma }_{-1},L},Q_{{\gamma }_{-1},L})=E_{A,B\mid L,{\gamma }_{-1}}(1-t{)}^{-n}\mathrm{.}$ The posterior of $L$ given $A,B,{\gamma }_{-1}$ has weights proportional to $1\mathrm{/}N(L)$; step 6.1 bounds the conditional remainder factor by $1+o(1)$ uniformly in $A,B,{\gamma }_{-1}$. Since $d-k+1\ge r\mathrm{/}3$, the overlap generating-function bound is uniform in $L,{\gamma }_{-1}$ and yields $E_{{\gamma }_{-1},L}[1+{\chi }^2({\bar{P}}_{{\gamma }_{-1},L},Q_{{\gamma }_{-1},L})]\le (1+o(1))\exp (C{k}^2{p}^{2v^2}\mathrm{/}r)=1+o(1),$ using step 1.1. For each fixed $({\gamma }_{-1},L)$, if $R=d\bar{P}\mathrm{/}dQ$, then $E_Q(R-1)=0$, so the positive and negative parts of $R-1$ have equal integrals, and the event $\{R\ge 1\}$ attains the supremum in [F9]; hence $\mathrm{TV}(\bar{P},Q)=\frac{1}{2}{E}_Q\mathrm{\mid }R-1\mathrm{\mid }$; [F10] bounds this by $\frac{1}{2}\sqrt{{\chi }^2(\bar{P},Q)}$. Finite Cauchy--Schwarz [F5] over the common prior weights on $({\gamma }_{-1},L)$ bounds the average conditional total variation by $\frac{1}{2}\sqrt{E_{{\gamma }_{-1},L}{\chi }^2}$, at most $1\mathrm{/}2$ after increasing $P_0$. The same mixing weights are used under bit $i=0$ and bit $i=1$, so the full sample-law mixtures have total variation at most $1\mathrm{/}2$ by the triangle inequality for the density integral. Their density affinity satisfies $\int \min (d{P}_{i,0},d{P}_{i,1})=1-\mathrm{TV}(P_{i,0},P_{i,1})\ge 1\mathrm{/}2.$

For parameters with $h$ different bits, apply their covariance difference to the vector that is one on the right block and zero elsewhere. Each changed bit contributes a distinct left-block coordinate of magnitude $sϵk$, independently of support choices, so the squared output norm is at least $h(sϵk{)}^2$ while the input squared norm is $r$. Hence $\mathrm{\parallel }{\mathrm{\Sigma }}_{\theta }-{\mathrm{\Sigma }}_{{\theta }^{\mathrm{\prime }}}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2\ge h(sϵk{)}^2\mathrm{/}r$. Given any measurable matrix estimator, choose a nearest finite covariance target with a fixed tie order. The finite distance comparisons are measurable: [F5] bounds the operator norm by the Frobenius norm, and its triangle inequality follows by applying the Euclidean triangle inequality to every unit vector, so distance to each fixed target is continuous. A wrong target decision forces squared estimation loss at least one quarter of the squared target separation. For each bit, the sum of its two conditional testing errors is at least the density affinity, since pointwise the test contributes at least the minimum of the two densities. By step 7.1, under the uniform prior each bit error probability is at least $1\mathrm{/}4$, so the average number of bit errors is at least $r\mathrm{/}4$. The maximal risk is at least the average risk and therefore at least $(sϵk{)}^2\mathrm{/}16$. Finally, $k\ge c\mathrm{/}[4(sϵ{)}^q]$ implies this is at least $b{c}^2{a}^{1-q}$ for a positive constant depending only on the fixed parameters.