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 R,there is a 中：Rd→R with k=O(e-2logn),such that Vx,y∈S: (1-e)x-yl2≤lφ(x)-(y)川l2≤(1+e)lx-y2(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 ϕ : ℝd → ℝk k = O(ϵ−2 log n) ∀x, y ∈ S : (1 − ϵ)∥x − y∥2 2 ≤ ∥ϕ(x) − ϕ(y)∥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