南京大学：《概率与计算 Probability and Computing》课程教学资源（课件讲稿）random6

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, ￾Au￾2 > 3k 2d ￾Au￾2 < k 2d with probability o( 1 n2 ) or New goal: O(n2) pairs treat (u ￾ v) as a vector, u￾v ⇥u￾v⇥ 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, ￾Au￾2 > 3k 2d ￾Au￾2 < 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, ￾Au￾2 > 3k 2d ￾Au￾2 < 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, ￾Au￾2 > 3k 2d ￾Au￾2 3k 2d ￾Z￾2 < k 2d or Y = (Y1,...,Yk, Yk+1,...,Yd) uniform random unit vector: