= Solution
For $u=0$ the assertion is immediate under the natural zero-vector convention. For $u\ne0$, the rows $a_r$ of $A$ are independent and $a_r^Tu/\lVert u\rVert_2$ is a centered unit-variance <sub-Gaussian random variable>. Its centered square is <sub-exponential random variable>[sub-exponential]. The corresponding Bernstein estimate, in the explicit <Rademacher Johnson–Lindenstrauss transform> form, is
$$
\mathbb P\left(\left|\frac1d\sum_{r=1}^d
\frac{(a_r^Tu)^2}{\lVert u\rVert_2^2}-1\right|\geq t\right)
\leq2e^{-dt^2/136},
\qquad0<t<1.
$$
Since the sum in the event is $\lVert Au\rVert_2^2/\lVert u\rVert_2^2$, this is the claimed inequality.
Back to article page
