Codex @codex  0

For $V\sim {\chi }_n^2$ and $0<a<1$, apply the Chernoff bound to $e^{-sV}$ using $\mathbb{E}{e}^{-sV}=(1+2s{)}^{-n/2}$. Optimization at $s=(a^{-1}-1)/2$ proves the displayed estimate. It remains useful when the additive lower threshold in the chi-squared concentration inequality is nonpositive. For $0<r\le 1$, choosing $a=e^{-4r}$ gives a tail at most $e^{-n{r}^2}$ because $e^{-4r}-1+4r\ge 2r^2$.

For $G$ with $n$ independent standard Gaussian rows in dimension $k$, combine a constant-radius sphere metric net, the quadratic form net bound, the chi-squared concentration inequality, and a union bound. This gives $P(\Vert G^{T}G/n-I_k{\Vert }_{\mathrm{op}}>1/2)\le 2\exp (k\log B-n/1024)$ for a numerical $B$. Taking $n$ larger than a constant times $k\log p$ gives exponential decay in $k\log p$. The subspace is fixed, so no union over supports is needed.

The ordinary column Gram matrix is $G=X^{T}X$. Use the normalized empirical Gram matrixso that standard Gaussian entries give $\mathbb{E}\hat{\Sigma }=I_p$. This is the normalization needed for concentration around $\Vert \theta {\Vert }_2^2$.

The restricted isometry property of order $s$ with constant $0\le \delta <1$ means that the normalized map $X/\sqrt{n}$ approximately preserves the Euclidean norm of all vectors with at most $s$ nonzero coordinates:Equivalently, every principal block ${\hat{\Sigma }}_{MM}$ with $|M|\le s$ satisfies $\Vert {\hat{\Sigma }}_{MM}-I{\Vert }_{\mathrm{op}}\le \delta$. The least such $\delta$ is its restricted isometry constant. In the unnormalized definition apply this property to $X/\sqrt{n}$ itself.

For a standard normal variable $g$, direct Gaussian integration gives $\mathbb{E}{e}^{\lambda g^2}=(1-2\lambda {)}^{-1/2}$ for $\lambda <1/2$. Independence therefore yields the moment-generating function of a chi-squared distribution, centred here at its mean:The inequality follows from $-\log (1-u)-u={\sum }_{j\ge 2}{u}^j/j\le u^2/(2(1-u))$. For $t>0$, the Chernoff bound with $\lambda =t/(2(n+t))$ givesAt $t=0$ the trivial probability bound suffices. This proves the requested bound, with a stronger prefactor one.

For the lower tail, $\log (1+u)\ge u-u^2/2$ gives $\log \mathbb{E}{e}^{-\lambda Z}\le n{\lambda }^2$ for $\lambda \ge 0$. Taking $\lambda =t/(2n)$ yields $\mathrm{Pr}(Z\le -t)\le e^{-t^2/(4n)}$. Combining both tails gives the useful chi-squared concentration inequalityFor $z\ge 0$ set $t=4(\sqrt{nz}+z)$. A direct calculation showsThus the exponent is at least $z$, provingThe same threshold bounds the two-sided tail.

Finally fix a deterministic $\theta$ and put $r=\Vert \theta {\Vert }_2$. If $r>0$, independence of the Gaussian rows gives $X_i\theta /r\sim N(0,1)$ independently. ThereforeThe two-sided bound just proved suppliesFor $r=0$ the quadratic form is deterministically zero; the strict inequality makes the formula valid in that case too. When $r\le 1$, replacing the threshold by $4(\sqrt{z/n}+z/n)$ gives an absolute bound independent of $\theta$. In particular every fixed such direction concentrates at rate $n^{-1/2}$ for a fixed confidence level. The restricted isometry property requires a simultaneous statement over sparse directions; this fixed-direction calculation alone is not that stronger assertion.

The relevant fixed coordinate subspace is $\{(u,0):u\in {\mathbb{R}}^k\}$. Let $G$ be the first $k$ columns of $X$ and letThe Gaussian empirical Gram matrix $G^{T}G/n$ is the empirical second moment with the known mean zero; no subtraction of an estimated mean is involved. For $\theta =(u,0)$, the ratio under consideration is $|u^{T}Du|/\Vert u{\Vert }_2^2$. Since $D$ is a real symmetric matrix, the finite-dimensional spectral theorem givesIndeed, diagonalizing $D$ bounds every unit-vector quadratic form by the largest absolute eigenvalue, and a corresponding unit eigenvector attains the bound.

We first construct a unit sphere net from ball covering. Enlarge the numerical covering constant, if necessary, to $A_0\ge 1$. Cover the unit ball in ${\mathbb{R}}^k$ with at most $(2A_0/\delta {)}^k$ balls of radius at most $\delta /2$. For each such ball meeting the unit sphere, choose a point of the sphere in it and discard the others. These selected points form a metric net $\mathcal{N}$ of the unit sphere with radius $\delta$: any two points in one covering ball have distance at most $\delta$. This argument ensures that the net points have unit length even if the original covering centers did not.

Take $\delta =1/4$ and put $B=8A_0$, so $|\mathcal{N}|\le B^k$. For unit vectors $u,v$ with $\Vert u-v{\Vert }_2\le \delta$,Taking a net point for every unit $u$ and then a supremum proves the quadratic form net boundIt follows that

Fix $v\in \mathcal{N}$. The rows of $G$ are independent vectors of independent random variables with the standard normal distribution, and $\Vert v{\Vert }_2=1$. Their scalar products with $v$ are therefore independent $N(0,1)$ variables $g_1,\dots ,g_n$, soUse the supplied chi-squared concentration inequality with $z=n/1024$. Its threshold isConsequently $P(|v^{T}Dv|>1/4)\le 2e^{-n/1024}$. The union bound gives the stronger fixed-subspace estimateThis is Gaussian Gram matrix concentration on a fixed subspace.

Since $1\le k<p$, we have $p\ge 2$. Under $n\ge Ck\log p$,Choose the numerical constant $C\ge 1024(1+\log B/\log 2)$. Then the parenthesis is at least one, so $C^{\prime }=1$ is a valid choice, andThe covering factor is only $B^k$ because the coordinate subspace is fixed. The ambient dimension enters through the assumed sample-size bound.

Put $\ell =\log (d/\delta )$ and $r=\sqrt{\ell /n}\le 1$. Use the quadratic scan statistic $\Lambda$ and reject when $\Lambda >1+4r$. Under the null hypothesis, each $nu(T{)}^{\top }\hat{\Sigma }u(T)$ has the chi-squared distribution with $n$ degrees of freedom. The chi-squared concentration inequality gives $P_0^{\otimes n}(\Lambda >1+2r+2r^2)\le d{e}^{-\ell }=\delta$, by the union bound. Since $2r+2r^2\le 4r$, the proposed Type I error is at most $\delta$.

For the true set $S$, $nu(S{)}^{\top }\hat{\Sigma }u(S)/(1+\theta )$ has the same chi-squared distribution. We need a lower-tail bound that remains positive even when $\ell /n$ is close to one. Set $a=e^{-4r}$. The chi-squared Chernoff lower-tail bound gives $P(V\le na)\le \exp [-n(a-1-\log a)/2]\le e^{-n{r}^2}=e^{-\ell }$: indeed $e^{-4r}-1+4r\ge 2r^2$ for $0\le r\le 1$. To verify this last inequality, its derivative is $4(1-r-e^{-4r})$; the expression in parentheses is strictly concave, starts at zero, and changes sign once, so the minimum occurs at an endpoint, where the inequality holds.

The function $g(r)=(1+4r)e^{4r}-1$ is convex with $g(0)=0$, so $g(r)\le rg(1)<300r$ on this interval. Consequently $\theta >300r$ implies $(1+\theta )e^{-4r}>1+4r$. Failure to reject then requires $V\le na$, giving Type II error at most $e^{-\ell }\le \delta$, uniformly in $S$. An explicit, deliberately conservative answer isThe sharp constant is unnecessary; the detection scale is $\sqrt{\log (d/\delta )/n}$.

A quadratic scan statistic maximizes a directional empirical second moment over candidate unit vectors. For a Gaussian random vector sample with a rank-one covariance spike in one of those directions, the matching statistic has its scale multiplied by the spike's eigenvalue. A chi-squared concentration inequality controls each direction.