Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 205 / 5 / Solution

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