Metric Embedding (X,dx) (Y,dy) low-distortion:For a small a 1 x1,x2∈X, 1dx(1,r2）≤dr(o(e),(r2l》≤adx(1,2）
Metric Embedding (X, dX) (Y, dY ) low-distortion: ⇥x1, x2 X, 1 dX(x1, x2) dY (⇥(x1), ⇥(x2)) dX(x1, x2) For a small 1
Dimension Reduction 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. Johnson-Lindenstrauss Theorem: For any 0<e<1,for any set V of n points in Rd, there is a mapΦ：Rd→R with k=O(lnn), such that Vu,v∈V, (1-e)川u-vl2≤川(u）)-p(v)川2≤(1+e)川u-vl2
Dimension Reduction 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. Johnson-Lindenstrauss Theorem: For any 0 < < 1, for any set V of n points in Rd , there is a map : Rd Rk with k = O(ln n), such that ⇥u, v V , (1 )⇤u v⇤2 ⇥ ⇤⇥(u) ⇥(v)⇤2 ⇥ (1 + )⇤u v⇤2
Johnson-Lindenstrauss Theorem Johnson-Lindenstrauss Theorem: For any 0<e<1,for any set V of n points in Rd, there is a map RdRh with k=O(Inn), such that Vu,v∈V, (1-e)川u-vl2≤I(u)-(u)川2≤(1+e)川u-vll2 (v)=Av. A is a random projection matrix
Johnson-Lindenstrauss Theorem For any 0 < < 1, for any set V of n points in Rd , there is a map : Rd Rk with k = O(ln n), such that ⇥u, v V , (1 )⇤u v⇤2 ⇥ ⇤⇥(u) ⇥(v)⇤2 ⇥ (1 + )⇤u v⇤2 • • A is a random projection matrix. (v) = Av. Johnson-Lindenstrauss Theorem:
Random Projection Random kxd matrix A: Projection onto a uniform random subspace. (Johnson-Lindenstrauss) (Dasgupta-Gupta) i.i.d.Gaussian entries. (Indyk-Motiwani) rows:A1.,A2.,...,Ak. ● i.i.d.-1/+1 entries. random orthogonal (Achlioptas) unit vectors∈Rd
Random Projection • Projection onto a uniform random subspace. (Johnson-Lindenstrauss) (Dasgupta-Gupta) • i.i.d. Gaussian entries. (Indyk-Motiwani) • i.i.d. -1/+1 entries. (Achlioptas) Random k×d matrix A: A1·, A2· rows: ,...,Ak· random orthogonal unit vectors Rd
Johnson-Lindenstrauss Theorem Let V be a set of n points in Rd. ●For some k=O(lnn). ●Let A be a random k×d matrix that projects onto a uniform random k-dimensional subspace. W.h.p.,u,v∈V, (for the case s=1/2) llu -ol2 ≤ 3‖lu-vl2 2 2 the projection
• • • W.h.p., ⇥u, v V , Let V be a set of n points in Rd. Let A be a random k d matrix that projects onto a uniform random k-dimensional subspace. For some k = O(ln n). (for the case ε=1/2) ⇤u v⇤2 2 ⇥ ⇥d k Au ⇥d k Av 2 ⇥ 3⇤u v⇤2 2 the projection Johnson-Lindenstrauss Theorem