Norm Preservation ·0≤e≤l,V set S of n points from Rd Random matrix A ERkxd withk=(e-2log n): Johnson-Lindenstrauss Theorem: With high probability(≥1-O(1/n)y:x,y∈S, (1-e)lx-y2≤IAx-Ay2≤(1+e)lx-y3 ☒ union bound 1-≤4品 over all O(n2) ≤1+e 个 pairs ofx,y∈S unit vector！ for any unit vector u ERd: Pr[lAu3-1><是a• , set of points from • Random matrix with : ∀0 ≤ ϵ ≤ 1 ∀ S n ℝd A ∈ ℝk×d k = (ϵ−2 log n) Norm Preservation Johnson-Lindenstrauss Theorem: With high probability ( ≥ 1 − O(1/n)): ∀x, y ∈ S, (1 − ϵ)∥x − y∥2 2 ≤ ∥Ax − Ay∥2 2 ≤ (1 + ϵ)∥x − y∥2 2 1 ￾ ✏  ￾ ￾ ￾ A (x￾y) kx￾yk2 ￾ ￾ ￾ 2 2  1 + ✏ unit vector! union bound over all O(n2) pairs of x, y ∈ S for any unit vector u ∈ ℝd : Pr ⇥￾ ￾kAuk2 2 ￾ 1 ￾ ￾ > ✏ ⇤ < 1 n3