AERAxd:each entry of A is chosen i.i.d.from ( for any unit vector u E Rd: Pr[I川Au3-1><志 k k ‖Aul3=入(Au)月 E[Au1-∑E[(Au] 2=1 2=1 recall: X~W(1,o),Y~N(2,o)→X+Y~N(1+2,o1+o) >( -套w)=() i-1 independently！for any unit vector u ∈ ℝd : Pr ⇥￾ ￾kAuk2 2 ￾ 1 ￾ ￾ > ✏ ⇤ < 1 n3 A ∈ ℝk×d : each entry of A is chosen i.i.d. from 𝒩 (0, 1 k ) kAuk2 2 = X k i=1 (Au) 2 i E ⇥ kAuk2 2 ⇤ = X k i=1 E ⇥ (Au) 2 i ⇤ (Au) 2 i = 0 @X d j=1 Aijuj 1 A 2 = N ✓ 0, 1 k ◆ Aij ⇠ N ✓ 0, 1 k ◆ linearity of expectation each i.i.d. (Au)i = X d j=1 Aijuj ⇠ N 0, Pd j=1 u2 j k ! recall: X ⇠ N ￾ µ1, ￾2 1 ￾ , Y ⇠ N ￾ µ2, ￾2 2 ￾ =) X + Y ⇠ N (µ1 + µ2, ￾2 1 + ￾2 2) independently!