Embeddings and Projections

Ramesh gave a series of talks centered around embeddings and projections in Euclidean space. These techniques have applications to a surprisingly wide variety of algorithmic problems.

Many algorithms in computational geometry, for example, suffer from the curse of dimensionality: they are exponential in the dimension of the ambient space in which the geometric objects such as points reside. Suppose one could somehow squash the points into a lower dimensional space: then we could be rid of the space. The Johnson-Lindenstrauss Lemma seeks to do precisely this. Of course nothing comes for free! What we can hope to do is to retain only some approximation of the original metric structure, and there is a tradeoff between how good the approximation is and how low a dimension we can come down to: to preserve all distances within a multiplicative factor $(1 + \epsilon)$, we can still go down to $\log n / \epsilon^2$ dimensions. How does one achieve this? The Probabilist Method! Choose a random subspace of that dimension and project! What does choosing a random subspace mean? Choose the normal to the hyperplane at random, which, in turn, means that each of its components must be chosen randomly and independently. In fact, to retain spherical symmetry, which is very useful in the arguments, one is led to choose the components to be normally distributed. Thereafter, some routine calculations with Chernoff bounds show that any unit vector is distorted by no more than a multiplicative factor of $(1 + \epsilon)s$ where $s$ does not depend on the points themselves. A good place to see the details is in some notes of Leonard Schulman [11].

Given an arbitrary finite metric represented by an edge-weighted graph (so that we are referring to the metric induced by the shortest path), can we realise the metric by an embedding into Euclidean space under the usual metrics? In the context of an NP-hard optimization problem on graphs called the sparsest cut, it turns out that one is interested in $\ell_1$ embeddings. Once again, it is not always possible to achieve a perfect embedding, but one can get an embedding with a multiplicative distortion factor of $O(\log n)$. The embedding due to Jean Bourgain is in terms of a family of subsets of the vertex set: each subset in the family corresponds to a dimension in Euclidean space, and the co-ordinate for vertex $v$ in dimension corresponding to the set $A$ is $d(v,A)$, the minimum distance of $v$ from the set $A$ (together with a scaling factor). For an appropriate choice of the family of subsets, we get the low distortion embedding. Bourgain showed that one can take the family $\bigcup_i {V \choose 2^i}$. Of course this is useless for algorithmic purposes, because this involves an exponential number of dimensions! However, the proof shows that one doesn't need all the sets: a polynomial sized random sample in each size of sets is sufficient. One can therefore alternatively say, as Ramesh did, that one should pick a random family of sets, just use different sampling rates. An account (not the best written though!) of this technique under the title ``The Geometry of Graphs'' is in [12].

For other graph problems, one requires something stronger: not just to preserve the length of edges, but perhaps to preserve the ``volume'' of simplices of vertices. An example of this kind is the NP-hard problem of bandwidth minimization: given a graph, embed it on a straight line so as to minimize the maximum stretch of an edge. This is the problem for which Feige was led to consider a generalization that would embed a graph so that the ``volume'' of any $k$ vertices of the graph is preserved. As a measure of the ``volume'' of $k$ vertices, Feige proposes the minimum spanning tree induced by those vertices, and seeks an embedding such that the Euclidean volume of the embedding of any $k$ vertices reflects the MST of those vertices faithfully. Feige achieves an approximation factor which is polynomial in $k$ and $\log n$. The idea of the embedding is inspired by the Bourgain technique but is considerably more involved with some deep geometric insights such as a Brunn-Minkowski type inequality. Feige told me that he was looking forward to comments by the referees but instead the editor accepted the paper without waiting for them! Both a testimony to the importance of the paper as well as an injunction for us to study it carefully. See the paper [5].