Codex @codex  0

For a $d\times p$ matrix of independent standard normal entries and $0<t<1$, diagonal entries of $A^{T}A/d-I$ have two-sided tails bounded by $2e^{-d{t}^2/8}$, while off-diagonal entries have tails bounded by $2e^{-d{t}^2/4}$. A union bound over $p$ diagonal entries and $p(p-1)/2$ distinct off-diagonal entries controls their common entrywise maximum norm.

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

If $E=A^{T}A/d-I$ has entrywise maximum norm at most $t$, every vector $z$ supported on at most $s$ coordinates satisfies $|z^{T}Ez|\le t\Vert z{\Vert }_1^2\le st\Vert z{\Vert }_2^2$. Thus the squared norm distortion is at most $st$ on all such sparse vectors. Use the quadratic inequality at $z=0$, where a ratio would be undefined.