= Solution
A centered <random variable> $X$ is <sub-Gaussian random variable>[sub-Gaussian] with parameter $a>0$ when
$$
\mathbb E e^{tX}\leq e^{a^2t^2/2}
$$
for 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$, then
$$
\mathbb P\!\left(\left|\frac1n\sum_{i=1}^n
\{U_iV_i-\mathbb E(U_iV_i)\}\right|\geq t\right)
\leq2\exp\!\left(-\frac{2nt^2}{\sigma^2(\sigma^2+t)}\right).
$$
Since $U^TV=\sum_iU_iV_i$, this is the required bound. It follows by observing that a product of sub-Gaussian variables is <sub-exponential random variable>[sub-exponential] and applying <Bernstein's inequality> to the independent centered products.
For any vector $\delta$ admissible in the definition of $\phi_\Sigma^2$, one has $\|\delta\|_1\leq4$. The <entrywise maximum norm> bound therefore implies
$$
|\delta^T(\Theta-\Sigma)\delta|
\leq\max_{j,k}|\Theta_{jk}-\Sigma_{jk}|\,\|\delta\|_1^2
\leq\frac{\phi_\Sigma^2}{2s}.
$$
By the definition of the <compatibility constant>, $\delta^T\Sigma\delta\geq\phi_\Sigma^2/s$, and hence
$$
\delta^T\Theta\delta\geq\frac{\phi_\Sigma^2}{2s}.
$$
Taking the infimum proves $\phi_\Theta^2\geq\phi_\Sigma^2/2$. This is the <stability of a compatibility constant under entrywise perturbation>.
Put $C=X^TX/n$. Applying the product concentration bound with the stated $t$ and using $t\leq\sigma^2/3$ gives, for every $j,k$,
$$
\mathbb P(|C_{jk}-\Sigma_{jk}|>t)
\leq2e^{-3\log(p+1)}=\frac2{(p+1)^3}.
$$
There are $p(p+1)/2$ distinct entries in the symmetric matrix, so the <union bound> shows that the event
$$
\mathcal E=\left\{\max_{j,k}|C_{jk}-\Sigma_{jk}|\leq t\right\}
$$
has probability at least $1-p/(p+1)^2\geq p/(p+1)$.
On $\mathcal E$, $|C_{jj}-1|\leq t$. Since $|\Sigma_{jk}|\leq1$ by <Cauchy-Schwarz inequality>[Cauchy-Schwarz], normalization of the sample columns gives
$$
|\widehat\Sigma_{jk}-\Sigma_{jk}|
=\left|\frac{C_{jk}}{\sqrt{C_{jj}C_{kk}}}-\Sigma_{jk}\right|
\leq\frac{2t}{1-t}.
$$
Choosing one coordinate of $S$ in the infimum shows $\phi_\Sigma^2\leq s$, so the assumed bound on $t$ is below one and, more precisely,
$$
t\leq\frac{\phi_\Sigma^2}{64s+\phi_\Sigma^2}
\quad\Longrightarrow\quad
\frac{2t}{1-t}\leq\frac{\phi_\Sigma^2}{32s}.
$$
The perturbation result now gives $\phi_{\widehat\Sigma}^2\geq\phi_\Sigma^2/2$ throughout $\mathcal E$, and therefore
$$
\mathbb P(\phi_{\widehat\Sigma}^2\geq\phi_\Sigma^2/2)\geq\frac p{p+1}.
$$
Back to article page
