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
A:projection onto a uniform W.h.p,u,v∈V, random k-subspace 那甲w很≥“ 2 Step I: Reduce to unit vectors
W.h.p., ⇥u, v V , A: projection onto a uniform random k-subspace ⇥d k Au ⇥d k Av 2 ⇥ 3⇤u v⇤2 2 ⇥d k Au ⇥d k Av 2 ⇥ ⇤u v⇤2 2 Step I: Reduce to unit vectors
O(n2)pairs A:projection onto a uniform random k-subspace W.h.p.,u,v∈V, -4「s 2 2 d M-a 2d treat (u)as a vector, is a unit vector New goal: V unit vector u, with probability o(是) IlAull2> d or lAul<2d
W.h.p., ⇥u, v V , A: projection onto a uniform random k-subspace ⇥d k Au ⇥d k Av 2 ⇥ 3⇤u v⇤2 2 ⇥d k Au ⇥d k Av 2 ⇥ ⇤u v⇤2 2 A (u v) ⇤u v⇤ 2 ⇥ k 2d A (u v) ⇤u v⇤ 2 ⇥ 3k 2d unit vector u, Au2 > 3k 2d Au2 < k 2d with probability o( 1 n2 ) or New goal: O(n2) pairs treat (u v) as a vector, uv ⇥uv⇥ is a unit vector
A:projection onto a uniform random k-subspace V unit vector u, with probability o() IlAull2> d or 14ul2<2d Step II: Random projection of fixed unit vector 0 Fixed projection of random unit vector
unit vector u, Au2 > 3k 2d Au2 < k 2d with probability o( 1 n2 ) or Step II: Random projection of fixed unit vector Fixed projection of random unit vector A: projection onto a uniform random k-subspace ⇔
A:projection onto a uniform random k-subspace V unit vector u, with probability o(是) IlAull2> 2d or 14ul2<2a probabilistically random equivalent unit vector fixed fixed unit vector subspace random subspace "inner-products are invariant under rotations
unit vector u, Au2 > 3k 2d Au2 < k 2d with probability o( 1 n2 ) or A: projection onto a uniform random k-subspace fixed unit vector random subspace fixed subspace random unit vector probabilistically equivalent “inner-products are invariant under rotations
A:projection onto a uniform random k-subspace V unit vector u, with probability o() IAull2> d or 14ul2 d or 112< k 2d
unit vector u, Au2 > 3k 2d Au2 3k 2d Z2 < k 2d or Y = (Y1,...,Yk, Yk+1,...,Yd) uniform random unit vector: