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=1
for 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 )
AERAxd each entry of A is chosen i.i.d.from () for any unit vector u E Rd: Pr[Aull3-1><志 k ‖AuI3=∑(A)月 (Au)i~W(0,) i.i.d. i=1 E[川AuI2]=1 〉 for i.i.d.Y1,Y2,...,Y~N0, =aB->日-r位医
for any unit vector u ∈ ℝd : Pr ⇥ kAuk2 2 1 > ✏ ⇤ < 1 n3 kAuk2 2 = X k i=1 (Au) 2 i (Au)i ⇠ N 0, 1 k i.i.d. Pr ⇥ kAuk2 2 1 > ✏ ⇤ = Pr " X k i=1 Y 2 i E " X k i=1 Y 2 i # > ✏ # for i.i.d. E ⇥ kAuk2 2 ⇤ = 1 Y1, Y2,...,Yk ⇠ N 0, 1 k A ∈ ℝk×d : each entry of A is chosen i.i.d. from 𝒩 (0, 1 k )
AERx:each entry of A is chosen i.i.d.from () for any unit vector u E Rd: Pr [Aull3 -1>< for i.i.d.Y,Y2,...,N(0) consider X;=√k.Y lw->d-2e空> Chernoff bound for /-distributions: For independent Pr[Σ，X>I+e<e X1,,Xk∈W(0,1)→ Pr t<)k<e-c
for any unit vector u ∈ ℝd : Pr ⇥ kAuk2 2 1 > ✏ ⇤ < 1 n3 Pr ⇥ kAuk2 2 1 > ✏ ⇤ = Pr " X k i=1 Y 2 i E " X k i=1 Y 2 i # > ✏ # for i.i.d. Y1, Y2,...,Yk ⇠ N 0, 1 k consider Xi = p k · Yi A ∈ ℝk×d : each entry of A is chosen i.i.d. from 𝒩 (0, 1 k ) Chernoff bound for -distributions: For independent χ2 X1, …, Xk ∈ 𝒩(0,1) ⟹ Pr [∑k i=1 X2 i > (1 + ϵ)k] < e−ϵ2 k/8 Pr [∑k i=1 X2 i < (1 − ϵ)k] < e−ϵ2 k/8
AER:each entry of A is chosen i.i.d.from () for any unit vector u E Rd: Pr[I川Au3-1><志 for i.i.d.X1,X2,...,XN(0,1) Pr[lAu2-1>=Pr∑x好>1+ekom∑x?<I-gk i=1 for suitable k=O(8-2log n) Chernoff bound for -distributions: For independent Pr (1ck <e- X1,,X∈W(0,1)→ Pr -k<e-B
for any unit vector u ∈ ℝd : Pr ⇥ kAuk2 2 1 > ✏ ⇤ < 1 n3 Pr ⇥ kAuk2 2 1 > ✏ ⇤ for i.i.d. = Pr " X k i=1 X2 i > (1 + ✏)k or X k i=1 X2 i < (1 ✏)k # < 1 n3 for suitable k = O(ε-2log n) X1, X2,...,Xk ⇠ N (0, 1) A ∈ ℝk×d : each entry of A is chosen i.i.d. from 𝒩 (0, 1 k ) Chernoff bound for -distributions: For independent χ2 X1, …, Xk ∈ 𝒩(0,1) ⟹ Pr [∑k i=1 X2 i > (1 + ϵ)k] < e−ϵ2 k/8 Pr [∑k i=1 X2 i < (1 − ϵ)k] < e−ϵ2 k/8
Chernoff bound for -distributions: For independent Pr[∑X>I+ek<eew8 X1,,X∈r(0,1)→ r[∑X<I-e0<ee for all >0:Pr 1 Eletsx] ≤e-1+,Ee“成买e 、家∫e(% XN(0,1) y=-2 :扁该与·点
Pr " X k i=1 X2 i > (1 + ✏)k # = Pr h ePk i=1 X2 i > e(1+✏)k i e(1+✏)k · E h ePk i=1 X2 i i = e(1+✏)k · Y k i=1 E h eX2 i i E h esX2 i = 1 p1 2s X ⇠ N (0, 1) for all λ>0: Chernoff bound for -distributions: For independent χ2 X1, …, Xk ∈ 𝒩(0,1) ⟹ Pr [∑k i=1 X2 i > (1 + ϵ)k] < e−ϵ2 k/8 Pr [∑k i=1 X2 i < (1 − ϵ)k] < e−ϵ2 k/8