Chernoff bound for -distributions: For independent Pr[∑>I+ek<et8 X1,,X∈r(0,1)→ Pr[∑1X<(I-e<es for all -0:Pr 好0-w ≤e+.EeAx]=e+.Ⅱ巴[ex] XN(0,1) ≤e()月 ≤e-cAk+22k forλ≤1/4 =e-e2k/8 choosing =8/4
for all λ>0: 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) e✏k ⇣ e p12 ⌘k e✏k+22k for λ<1/4 = e choosing λ = ε/4 ✏ 2k/8 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
Johonson-Linenstrauss Theorem (Johnson-Lindenstrauss 1984) "In Euclidian space,it is always possible to embed a set of n points in arbitrary dimension to O(log n)dimension with constant distortion. Theorem (Johnson-Lindenstrauss 1984): VO<e<1,for any set S of n points from Rd,there is a A∈Rkxd with k=O(e-2logn),such that Vx,y∈S: (1-e)x-yl2≤‖Ax-Ay2≤(1+e)lx-yl2 ·The probabilistic method:for random A∈Rkxd rVx,y∈s:-er-y服sar-A3≤1+6x-yl明=1-o(日） w.h.p
(Johnson-Lindenstrauss 1984) Johonson-Linenstrauss Theorem Theorem (Johnson-Lindenstrauss 1984): , for any set of points from , there is a with , such that ∀0 < ϵ < 1 S n ℝd A ∈ ℝk×d k = O(ϵ−2 log n) ∀x, y ∈ S : (1 − ϵ)∥x − y∥2 2 ≤ ∥Ax − Ay∥2 2 ≤ (1 + ϵ)∥x − y∥2 2 “In Euclidian space, it is always possible to embed a set of n points in arbitrary dimension to O(log n) dimension with constant distortion.” • The probabilistic method: for random A ∈ ℝk×d Pr[∀x, y ∈ S : (1 − ϵ)∥x − y∥2 2 ≤ ∥Ax − Ay∥2 2 ≤ (1 + ϵ)∥x − y∥2 2] = 1 − O ( 1 n) w.h.p
Theorem (Johnson-Lindenstrauss 1984): VO<e<1,for any set S of n points from R,there is a A∈Rxd with k=O(e-2logn),such that Vx,y∈S: (1-e)lx-y3≤Ax-Ay3≤(1+elx-y3 ·The probabilistic method:for random A∈Rkxd Pr[xy∈s:-ok-脂≤r-a服≤+or-明=1-o(日) Efficient construction of random A Rkxd: projection onto uniform random k-dimensional subspace; (Johnson-Lindenstrauss;Dasgupta-Gupta) independent Gaussian entries;(Indyk-Motwani) i.i.d.-1/+1 entries;(Achlioptas)
Theorem (Johnson-Lindenstrauss 1984): , for any set of points from , there is a with , such that ∀0 < ϵ < 1 S n ℝd A ∈ ℝk×d k = O(ϵ−2 log n) ∀x, y ∈ S : (1 − ϵ)∥x − y∥2 2 ≤ ∥Ax − Ay∥2 2 ≤ (1 + ϵ)∥x − y∥2 2 • The probabilistic method: for random A ∈ ℝk×d Pr[∀x, y ∈ S : (1 − ϵ)∥x − y∥2 2 ≤ ∥Ax − Ay∥2 2 ≤ (1 + ϵ)∥x − y∥2 2] = 1 − O ( 1 n) • Efficient construction of random : • projection onto uniform random k-dimensional subspace; (Johnson-Lindenstrauss; Dasgupta-Gupta) • independent Gaussian entries; (Indyk-Motwani) • i.i.d. -1/+1 entries; (Achlioptas) A ∈ ℝk×d
Dimension Reduction Input:n points... Output::n pointsy1,Jy2,,yn∈Rks.t.H1≤i,j≤n: (1-e)x:-xl3≤y:-y2≤(1+e);-3 for some suitable k-O(e-2l0gn): J-L Transformation(uniform k-dim subspace): The k rows A1,...,Ak of A ERxd are orthogonal unit vectors eR chosen uniform at random; ri=12m做%=V层4 A ERxd:projection onto a uniform k-dimensional subspace
• for some suitable k = O(ϵ : −2 log n) Dimension Reduction J-L Transformation (uniform k-dim subspace): The rows of are orthogonal unit vectors chosen uniform at random; For : let ; k A1,…, Ak A ∈ ℝk×d ∈ ℝd i = 1,2,…, n yi = d k Axi • projection onto a uniform k-dimensional subspace A ∈ ℝk×d : Input: points Output: points s.t. n x1, x2, …, xn ∈ ℝd n y1, y2, …, yn ∈ ℝk ∀1 ≤ i, j ≤ n : (1 − ϵ)∥xi − xj ∥2 2 ≤ ∥yi − yj ∥2 2 ≤ (1 + ϵ)∥xi − xj ∥2 2