= Solution
The ordinary column <Gram matrix> is $G=X^TX$. Use the normalized empirical <Gram matrix>
$$
\widehat\Sigma=\frac1nX^TX,
$$
so that standard Gaussian entries give $\mathbb E\widehat\Sigma=I_p$. This is the normalization needed for concentration around $\|\theta\|_2^2$.
The <restricted isometry property> of order $s$ with constant $0\leq\delta<1$ means that the normalized map $X/\sqrt n$ approximately preserves the <Euclidean norm> of all vectors with at most $s$ nonzero coordinates:
$$
(1-\delta)\|u\|_2^2\leq\frac1n\|Xu\|_2^2\leq(1+\delta)\|u\|_2^2.
$$
Equivalently, every principal block $\widehat\Sigma_{MM}$ with $|M|\leq s$ satisfies $\|\widehat\Sigma_{MM}-I\|_{\mathrm{op}}\leq\delta$. The least such $\delta$ is its <restricted isometry constant>. In the unnormalized definition apply this property to $X/\sqrt n$ itself.
For a standard normal variable $g$, direct Gaussian integration gives $\mathbb E e^{\lambda g^2}=(1-2\lambda)^{-1/2}$ for $\lambda<1/2$. <Independence> therefore yields the <moment-generating function of a chi-squared distribution>, centred here at its mean:
$$
\log\mathbb E e^{\lambda Z}=n\left(-\lambda-\tfrac12\log(1-2\lambda)\right)\leq\frac{n\lambda^2}{1-2\lambda},\qquad0\leq\lambda<\tfrac12.
$$
The inequality follows from $-\log(1-u)-u=\sum_{j\geq2}u^j/j\leq u^2/(2(1-u))$. For $t>0$, the <Chernoff bound> with $\lambda=t/(2(n+t))$ gives
$$
\Pr(Z\geq t)\leq\exp\left(-\lambda t+\frac{n\lambda^2}{1-2\lambda}\right)=\exp\left(-\frac{t^2}{4(n+t)}\right).
$$
At $t=0$ the trivial <probability> bound suffices. This proves the requested bound, with a stronger prefactor one.
For the lower tail, $\log(1+u)\geq u-u^2/2$ gives $\log\mathbb E e^{-\lambda Z}\leq n\lambda^2$ for $\lambda\geq0$. Taking $\lambda=t/(2n)$ yields $\Pr(Z\leq-t)\leq e^{-t^2/(4n)}$. Combining both tails gives the useful <chi-squared concentration inequality>
$$
\boxed{\Pr(|Z|\geq t)\leq2\exp\left(-\frac{t^2}{4(n+t)}\right),\qquad t\geq0.}
$$
For $z\geq0$ set $t=4(\sqrt{nz}+z)$. A direct calculation shows
$$
t^2-4z(n+t)=12nz+16z\sqrt{nz}\geq0.
$$
Thus the exponent is at least $z$, proving
$$
\boxed{\Pr(Z\geq4(\sqrt{nz}+z))\leq2e^{-z}.}
$$
The same threshold bounds the two-sided tail.
Finally fix a deterministic $\theta$ and put $r=\|\theta\|_2$. If $r>0$, <independence> of the Gaussian rows gives $X_i\theta/r\sim N(0,1)$ independently. Therefore
$$
\theta^T\widehat\Sigma\theta=r^2\left(1+\frac Zn\right).
$$
The two-sided bound just proved supplies
$$
\boxed{\Pr\!\left(\left|\theta^T\widehat\Sigma\theta-\|\theta\|_2^2\right|>4\|\theta\|_2^2\left(\sqrt{\frac zn}+\frac zn\right)\right)\leq2e^{-z}.}
$$
For $r=0$ the <quadratic form> is deterministically zero; the strict inequality makes the formula valid in that case too. When $r\leq1$, replacing the threshold by $4(\sqrt{z/n}+z/n)$ gives an absolute bound <independent> of $\theta$. In particular every fixed such direction concentrates at rate $n^{-1/2}$ for a fixed confidence level. The <restricted isometry property> requires a simultaneous statement over sparse directions; this fixed-direction calculation alone is not that stronger assertion.
Back to article page
