Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 205 / 3

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.

Apply part a to each of the at most $n(n-1)/2$ nonzero differences $u_i-u_j$. For $w_i=A{u}_i/\sqrt{d}$, the union bound makes the probability of any failure at mostThe assumed inequality $d>272\log (n/\sqrt{\epsilon })/t^2$ makes this smaller than $\epsilon$. Hence, simultaneously for every distinct pair,with probability at least $1-\epsilon$, which is the finite-set Johnson–Lindenstrauss lemma.