Lecture 17: Johnson-Lindenstrauss Theorem (Cont.), Dvoretsky’s Theorem

18.409 An Algorithmist’s Toolkit Lecture 17 Lecturer: Jonathan Kelner 1 Johnson-Lindenstrauss Theorem 1.1 Recap We first recap a theorem (isoperimetric inequality) and a lemma (concentration) from last time: Theorem 1 (Measure concentration on the sphere) Let Sn−1 be the unit sphere in Rn and A ∈ Sn−1 be a measurable set with vol(A) ≥ 1/2, and let Aε denote the set of points of Sn−1 with distance at most ε 2 from A. Then vol(Aε ) ≥ 1 − e−nε /2 . This theorem basically says that: When we get a set A which is greater or equal to half of the sphere, if we further incorporate points at most ε away from A, we almost have the whole sphere. Definition 2 (c-Lipschitz) A function f : A → B is c-Lipschitz if, for any u, v ∈ A, we have kf (u) − f (v)k ≤ c · ku − vk For a unit vector x ∈ Sn−1 , the projection of the first k dimension is a 1-Lipschitz function,: q f (x) = x21 + x22 + · · · + x2k p Lemma 3 For a unit vector x ∈ Sn−1 , and f (x) = x21 + x22 + · · · + x2k . Let x be a vector randomly chosen with uniform distribution from Sn−1 and M be the median of f (x). Then f (x) is sharply concentrated with: 2 P r[|f (x) − M | ≥ t] ≤ 2e−t 1.2 n/2 Metric Embedding Definition 4 (D-embedding) Suppose that X = {x1 , x2 , · · · xn } is a finite set, d is a metric on X, and f : X → Rk is 1-Lipschitz, with kf (xi ) − f (xj )k ≤ d(xi , xj ). The “distortion” of f is the minimum D for which kf (xi ) − f (xj )k ≤ d(xi , xj ) ≤ Dkf (xi ) − f (xj )k for some positive constant α. We refer to f as a D-embedding of X. Claim of Johnson-Lindenstrauss Theorem: The Euclidean metric on any finite set X (a bunch of high dimensional points) can be embedded with distortion D = 1 + ε in Rk for k = O(ε−2 log n). If we lose ε (ε = 0), it becomes almost impossible to do better than that in Rn . Nevertheless, it is not hard to construct a counter example to this: a simplex of n + 1 points. The Johnson-Lindenstrauss theorem gives us an interesting result: if we project x to a random subspace, the projection y give us an approximate length of x for some fixed multiplication factor c, i.e. kxk ∼ c · kyk. And c · y is embedded with distortion D = 1 + ε. 1.3 Proof of the Theorem Next, we provide a more precise statement about Johnson-Lindenstrauss Theorem: 17-1 Theorem 5 (Johnson-Lindenstrauss) Let X = {x1 , x2 , · · · xn } ∈ Rm (for any m) and let k = O(ε−2 log n). For: • L ⊆ Rm be a uniform random k dimensional subspace. • {y1 , y2 , · · · yn } be projections of xi on L. k • yi0 = cyi for some fixed constant c, and c = Θ( m ) Then, with high probability L is a (1 + ε)-embedding of X into Rk , i.e. for xi , xj ∈ X kxi − xj k ≤ kyi0 − yj0 k ≤ (1 + ε)kxi − xj k Proof Let ΠL : Rm → L be the orthogonal projection of Rm vector into subspace L. For xi , xj ∈ X, we let x be the normalized unit vector of xi − xj , and we need to prove that (1 − φ) · M kxk ≤ kΠL (x)k ≤ (1 + φ) · M kxk p holds with high probability, where M is the median of the of the function f = x21 + · · · + x2m . Following definition 4, this shows that the mapping ΠL is a D-embedding of X into Rk with D = 1+φ 1−φ . ε/3 We let φ = 3ε so that D = 11+ −ε/3 ≤ 1 + ε. Since kxk = 1, it is equivalent to showing that the following inequality holds with high probability ε (1) |kΠL (x)k − M | < M 3 Lemma 3 describes the case when we have a random unit vector and project it onto a fixed subspace. It is actually identical to fixing a vector and projecting it onto a random subspace (we will describe how this random subspace is generated in the next subsection). We use Lemma 3 and plug in t = 3ε M ; the probability inequality (1) does not hold is bounded by h 2 ε i P r |kΠL (x)k − M | ≥ M ≤ 4e−t m/2 3 2 2 = 4e−ε M m/18 2 ≤ 4e−ε k/72 ≤ 1/m2 q k ), Line 4 holds since k = O(ε−2 log n) (for further details, please see [1]). Line 3 holds since M = Ω( m based on the following reasoning: We have that X 1 = E[kXk2 ] = E[x2i ], which implies that E[x2i ] = 1 m. Consequently, 2 k = E[f 2 ] ≤ Pr[f ≤ M + t](M + t)2 + Pr[f > M + t] max(f 2 ) ≤ (M + t)2 + 2e−t m/2 , m q q Pk k k where we used the fact that f 2 = i=1 x2i . Taking t = Θ( m ), we have that M = Ω( m ). 17-2 1.4 Random Subspace Here we describe how a random subspace is generated. We first provide a quick review about Gaussians, a multivariate Gaussian has PDF: 1 1 exp(− (x − µ)T Σ−1 (x − µ)) px (x1 , x2 , · · · , xN ) = 2 (2π)N/2 |Σ|1/2 where Σ is a nonsingular covariance matrix and vector µ is the mean of x. Gaussians have several nice properties. The following operations on Gaussian variables also yield Gaussian variables: • Project onto a lower dimensional subspace. • Restrict to a lower dimensional subspace, i.e. conditional probability. • Any linear operations. In addition, we can generate a vector with multi-dimensional Gaussian distribution by picking each coordinate according to a 1-dimensional Gaussian distribution. How do we generate a random vector from a sphere? The idea here is to pick a point from a multidimensional Gaussian distribution (generate √ each coordinate with mean = 0 and variance = 1, N (0, 1)) so most n-dimensional vectors have norm n. As the shape of an independent Gaussian distribution’s PDF is symmetric, this procedure does indeed generate a point randomly and uniformly from a sphere (after normalizing it). Generating a random vector from a uniform distribution does not work, since it is not sampling uniformly from a sphere after normalization. How do we get a random projection? This is no more than sampling n × k times from a N (0, 1) gaussian distributions. Each k samples are grouped to form a k-dimensional vector, so we have n total vectors: v1 , v2 , · · · vn . We can simply orthonormalize these vectors, denoted as v̂i , and form the random subspace L:   .. .. .. . .   .  v̂1 v̂2 · · · v̂n    .. .. .. . . . 1.5 Applications of Johnson-Lindenstrauss Theorem The Johnson-Lindenstrauss Theorem is very useful in several application areas, since it can approximately solve many problems. Here we illustrate some of them: • Proximity Problems : This is an immediate application of the J-L Theorem. This is the case when we get a set of points in a high dimensional space Rd and we want to compute any property defined in terms of distance between points. Using the J-L theorem, we can actually solve the problem in a lower dimensional space (up to a distortion factor). Example problems here include closest pair, furthest pair, minimum spanning tree, minimum cost matching, and various clustering problems. • On-line Problems : The problems of this type involve answering queries in a high dimensional space. This is usually done through partitioning a high dimensional space according to some error (distance) measure. However, this operation tends to be exponentially dependent on the dimension of the space,
d e.g., 1ε (referred to as the “curse of dimensionality”). Projecting points of higher dimensional space into lower dimensional space significantly helps with these types of problems. • Data Stream/Storage Problem : We obtain data in a stream but we cannot store it all due to some storage space restriction. One way of dealing with it is to maintain a count for each data entry and then see how the counts are distributed. The idea is to provide “sketches” of such data based on the J-L Theorem. For further details, please refer to Piotr Indyk’s course and his survey paper. In summary, applications that are related to dimensionality reduction are very likely to be a good platform for the J-L Theorem. 17-3 2 Dvoretsky’s Theorem Dvoretsky’s Theorem, proved by Aryeh Dvoretsky in his article “A Theorem on Convex Bodies and Applications to Banach Spaces” in 1959, tries to answer the following question: • Let C be an origin-symmetric convex body in Rn . • S ⊆ Rn be a vector subspace. • We would like to know: does Y = C ∩ S look like a sphere? Furthermore, for how high a dimension (we denote it as k) does there exist an S for which this occurs? A formal statement of Y ’s similarity to a sphere can be characterized by whether Y has a small Banach-Mazur distance to the sphere, i.e. if there exists a linear transformation such that Sk−1 (1) ≤ Y ≤ Sk−1 (1 + ε) where Sk−1 (r) is denoted as a sphere with radius r. It turns out that k varies with different types of convex bodies: for a ellipsoid k = n, for a cross-polytope k = Θ(n), and for a cube is k = log(n). It turns out that the cube case is the worst case scenario. Here is a formal statement of Dvoretsky’s Theorem: Theorem 6 (Dvoretsky) There is a positive constant c > 0 such that, for all ε and n, every n-dimensional origin-symmetric convex body has a section within distance 1 + ε of the unit ball of dimension k≥ cε2 log n log(1 + ε−1 ) Instead of providing the whole proof, we give a sketch of the proof here: 1. When we are given an origin-symmetric convex body, denoted as C, it defines some norm with respect to the convex body: C → k · kC . 2. We need a subspace S to be spherical. It is basically saying that when we take any vector θ on S, then kθkC is approximately constant. 3. This is similar to concentration of measures which we have shown before. It basically says that when we have a function defined as a norm f : θ → kθkC , it is precisely concentrated for every θ on the sphere (i.e. every kθkC is close to median). 4. This is similar to Johnson-Lindenstrauss except that we need every vector in k-dimensional subspace satisfying point 2 (In the J-L theorem, we prove that most of the vectors (points) are close to a fixed constant, i.e. median). 5. What we do is to put a fine “mesh” on the k-dimensional subspace and show that every point on the grid is right. The number of points we need to check is approximately O(( 4δ )k ) where δ is the error. We can see that it is exponentially dependent on k and it looks similar to the dependency of k in the J-L theorem. For further details of the proof, please see [2]. References 1. Sariel Har-Peled, “Geometric Approximation Algorithms”, http://valis.cs.uiuc.edu/∼sariel/teach/notes/aprx 2. Aryeh Dvoretzky, “Some results on convex bodies and Banach spaces”, Proceedings of the National Academy of Sciences, 1959. 17-4