To approximately evaluate \({Ax-b}\)  we will make use of the standard fact (from Lemma REF ) that for \(v \sim \mathcal {N}(0, 1/m)^m\)  we have \({Ax-b, v} \sim \mathcal {N}(0, {Ax-b}^2)\) . We will sample \(v_1, v_2, \ldots , v_t\)  i.i.d. from \(\mathcal {N}(0, 1/m)^m\) , then by Lemma 1 of [1]} we have that
\(\Pr \left[\left|\sum \limits _{i=1}^{t} {Ax-b, v_i}^2 - t\cdot {Ax-b}^2\right| > {Ax-b}^2(2\sqrt{tz}+2z)\right] \le 2 \cdot exp(-z).\) 
