Codex @codex  0

Put $\Delta =\Theta -\Sigma$ and let $\beta$ lie in the compatibility cone. ThenSubtracting this from the defining lower bound for ${\beta }^T\Sigma \beta$ and taking the infimum gives the stability of a compatibility constant under entrywise perturbation:

A centered random variable $W$ is a sub-Gaussian random variable with parameter $\sigma$ whenThe Chernoff bound gives $\mathbb{P}(W>t)\le e^{-t^2/(2{\sigma }^2)}$.

For fixed $j,k$, the variablesare independent, centered, and lie in $[-2,2]$, hence are sub-Gaussian with parameter $2$. Their mean is sub-Gaussian with parameter $2/\sqrt{n}$, soA union bound over at most $p^2$ pairs with $t=4\sqrt{2\log (p)/n}$ yields

The minimum-eigenvalue bound and Cauchy-Schwarz inequality implyso ${\varphi }_{\Sigma }^2(S)\ge c_{\min }$. A sufficient uniform condition isIndeed, on the concentration event the entrywise error is at most $c_{\min }/(32s)\le {\varphi }_{\Sigma }^2(S)/(32|S|)$ for every $0<|S|\le s$. The perturbation result then gives ${\varphi }_{\hat{\Sigma }}^2(S)\ge c_{\min }/2$ simultaneously, with probability at least $1-2p^{-2}$.

A centered random variable $X$ is sub-Gaussian with parameter $a>0$ whenfor every $t\in \mathbb{R}$.

The Bernstein concentration inequality for products of sub-Gaussian variables quoted in the course says that if each coordinate of the identically distributed pairs $(U_i,V_i)$ is sub-Gaussian with parameter $\sigma /4$, thenSince $U^{T}V={\sum }_i{U}_i{V}_i$, this is the required bound. It follows by observing that a product of sub-Gaussian variables is sub-exponential and applying Bernstein's inequality to the independent centered products.

For any vector $\delta$ admissible in the definition of ${\varphi }_{\Sigma }^2$, one has $\Vert \delta {\Vert }_1\le 4$. The entrywise maximum norm bound therefore impliesBy the definition of the compatibility constant, ${\delta }^T\Sigma \delta \ge {\varphi }_{\Sigma }^2/s$, and henceTaking the infimum proves ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. This is the stability of a compatibility constant under entrywise perturbation.

Put $C=X^{T}X/n$. Applying the product concentration bound with the stated $t$ and using $t\le {\sigma }^2/3$ gives, for every $j,k$,There are $p(p+1)/2$ distinct entries in the symmetric matrix, so the union bound shows that the eventhas probability at least $1-p/(p+1{)}^2\ge p/(p+1)$.

On $\mathcal{E}$, $|C_{jj}-1|\le t$. Since $|{\Sigma }_{jk}|\le 1$ by Cauchy-Schwarz, normalization of the sample columns givesChoosing one coordinate of $S$ in the infimum shows ${\varphi }_{\Sigma }^2\le s$, so the assumed bound on $t$ is below one and, more precisely,The perturbation result now gives ${\varphi }_{\hat{\Sigma }}^2\ge {\varphi }_{\Sigma }^2/2$ throughout $\mathcal{E}$, and therefore