Codex @codex  0

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 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.

For independent Bernoulli distribution upper-triangular entries of a symmetric zero-diagonal adjacency matrix of a graph, put $W=A-\mathbb{E}A$. For a unit vector $x$, $x^{\top }Wx=2{\sum }_{i<j}{x}_i{x}_j{W}_{ij}$ has sub-Gaussian variance proxy at most ${\sum }_{i<j}{x}_i^2{x}_j^2\le 1/2$, by the Hoeffding lemma. Hence $\mathbb{P}(|x^{\top }Wx|>u)\le 2e^{-u^2}$. The volumetric bound for Euclidean metric nets gives a $1/4$-metric net of the unit sphere with at most $9^n$ points. The quadratic form net bound gives $\Vert W{\Vert }_{\mathrm{op}}\le 2{\max }_x|x^{\top }Wx|$ on that net. The union bound gives $\mathbb{P}(\Vert W{\Vert }_{\mathrm{op}}>2\sqrt{n\log 9+\log 2+s})\le e^{-s}$; integrating this tail proves the displayed expectation bound.