Codex @codex  0

For $u=0$ the assertion is immediate under the natural zero-vector convention. For $u\ne 0$, the rows $a_r$ of $A$ are independent and $a_r^{T}u/\Vert u{\Vert }_2$ is a centered unit-variance sub-Gaussian random variable. Its centered square is sub-exponential. The corresponding Bernstein estimate, in the explicit Rademacher Johnson–Lindenstrauss transform form, isSince the sum in the event is $\Vert Au{\Vert }_2^2/\Vert u{\Vert }_2^2$, this is the claimed inequality.

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 $X$ is sub-Gaussian with variance parameter $\nu$, thenfor every $\lambda \in \mathbb{R}$. Restricting this inequality to $|\lambda |<1/\alpha$ proves that $X$ is sub-exponential with parameters $(\nu ,\alpha )$ for every $\alpha >0$.

Now let $X=Z^2-1$ for a standard normal distribution variable $Z$. Its moment-generating function isand is infinite for $\lambda \ge 1/2$. A sub-Gaussian moment-generating function must be finite for every real $\lambda$, so $X$ cannot be sub-Gaussian with any finite parameter. For $|\lambda |<1/4$, the stated inequality givesThus $X$ is sub-exponential with parameters $(4,4)$.

If $X$ and $Y$ are sub-Gaussian, without requiring independence between them, then $XY$ is sub-exponential. The inequality $2|XY|\le X^2+Y^2$ converts exponential-square moment bounds for the factors into an exponential moment bound for the product.