Algorithms and Complexity Seminar
Thursday, February 14, 2008, 4:00-5:15pm in 32-G575.
On the Computational Near-Optimality of Random Projection
Anastasios Sidiropoulos (MIT CSAIL)
We consider the problem of computing a minimum-distortion embedding of
a finite metric space into a low-dimensional Euclidean space. It has
been shown by Matousek [Mat90] that for any d\geq 1, any n-point
metric can be embedded into R^d with distortion ~O(n^{2/d}) via a
random projection, and that in the worst case this bound is
essentially optimal. This clearly also implies an
~O(n^{2/d})-approximation algorithm for minimizing the distortion. We
show that for any fixed d\geq 2, there is no polynomial-time algorithm
for embedding into R^d, with approximation ratio better than
Omega(n^{1/(17d)}), unless P=NP. Our result establishes that random
projection is not too far, concerning the dependence on d, from the
best possible approximation algorithm for this problem.
Our proof uses a result from Combinatorial Topology due to Sarkaria,
that characterises the embeddability of a simplicial complex in terms
of the chromatic number of a certain Kneser graph.
The talk will be self-contained.
Joink work with Jiri Matousek
Host: Ning Xie
(The Algorithms
and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)