Dimension Reduction Input:n points...d Output::n pointsy1,Jy2,,yn∈Rks.t.H1≤i,j≤n: (1-e)x:-x3≤ly:-yl3≤(1+e)川；-x3 for some suitablek=O(e-2log n): J-L Transformation (i.i.d.Gaussian entries): Entries of A Rkxd are chosen i.i.d.from(0,1/k); (Gaussian distribution with mean 0 and variance 1/k) For i=1,2,...,n:let yi=Ax Gaussian random variable X~(u,o2): Px≤= E[X]= 202 dx Var[X]=o2• for some suitable k = O(ϵ : −2 log n) Dimension Reduction J-L Transformation (i.i.d. Gaussian entries): Entries of are chosen i.i.d. from ; (Gaussian distribution with mean 0 and variance ) For : let ; A ∈ ℝk×d 𝒩(0,1/k) 1/k i = 1,2,…, n yi = Axi • Gaussian random variable X ∼ 𝒩(μ, σ : 2 ) Pr[X ≤ t] = ∫ t −∞ 1 2πσ2 e −(x − μ) 2 2σ2 dx 𝔼[X] = μ Var[X] = σ2 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