AERxd:each entry of A is chosen i.i.d.from () for any unit vector u E Rd: Pr [Aul -1>e< k ‖AuI3=入(Au)层 E[Au1-∑E[(Aw月 i=1 i=1 (Au)iN(0,) i.i.d. ) E[(Au月]=Var[(Au)月+E[(Au2=府 > E[川Au3]=E[(Au)2]=1 2=1for any unit vector u ∈ ℝd : Pr ⇥￾ ￾kAuk2 2 ￾ 1 ￾ ￾ > ✏ ⇤ < 1 n3 kAuk2 2 = X k i=1 (Au) 2 i E ⇥ kAuk2 2 ⇤ = X k i=1 E ⇥ (Au) 2 i ⇤ linearity of expectation E ⇥ (Au) 2 i ⇤ = Var[(Au)i] + E [(Au)i] 2 = 1 k (Au)i ⇠ N ￾ 0, 1 k ￾ i.i.d. = X k i=1 E ⇥ (Au) 2 i ⇤ E ⇥ kAuk2 2 ⇤ = 1 A ∈ ℝk×d : each entry of A is chosen i.i.d. from 𝒩 (0, 1 k )