TITLE   : Advances in Metric Embedding Theory

AUTHORS : Ittai Abraham, Yair Bartal, Ofer Neiman

ABSTRACT:

Metric Embedding plays an important role in a vast range of
application areas such as computer vision, computational biology,
machine learning, networking, statistics, and mathematical
psychology, to name a few.

The theory of metric embedding received much attention in recent
years by mathematicians as well as computer scientists and has
been applied in many algorithmic applications.

 A cornerstone of the field is a celebrated theorem of Bourgain which states
 that every finite metric space on $n$ points embeds in Euclidean space
 with $O(\log n)$ distortion.

 Bourgain's result is best possible when
considering the worst case distortion over all pairs of points in
the metric space. Yet, it is possible that an embedding can do
much better in terms of the \emph{average distortion}.

Indeed, in most practical applications of metric embedding the
main criteria for the quality of an embedding is its
\emph{average} distortion over all pairs.

In this paper we provide an embedding with {\em constant} average
distortion for arbitrary metric spaces, while maintaining the same
worst case bound provided by Bourgain's theorem.

In fact, our embedding possesses a much stronger property. We
define the \emph{$\ell_q$-distortion} of a uniformly distributed
pair of points. Our embedding achieves the best possible
$\ell_q$-distortion for all $1 \leq q \leq \infty$
\emph{simultaneously}.

These results have several algorithmic implications, e.g. an
$O(1)$ approximation for the unweighted uncapacitated quadratic
assignment problem.

 The results are based on novel embedding methods which
improve on previous methods in another important aspect: the
\emph{dimension}.

The dimension of an embedding is of very high importance in
particular in applications and much effort has been invested in
analyzing it. However, no previous result improved the bound on
the dimension which can be derived from Bourgain's embedding.

We prove that any metric space on $n$ points embeds into $L_p$
with distortion $O(\log n)$ in dimension $O(\log n)$. This
provides an \emph{optimal} bound on the dimension of the
embedding.

Somewhat surprisingly, we show that a further small improvement is
possible at a small price in the distortion, obtaining an
embedding with distortion $O(\log^{1+\theta} n)$ in \emph{optimal}
dimension $O(\theta^{-1}\log n/\log\log n)$, for any $\theta >0$.
It is worth noting that with the small loss in the distortion this
improves upon the best known embedding of arbitrary spaces into
\emph{Euclidean} space, where dimension reduction is used.

Our techniques also allow to obtain the optimal distortion for
embedding into $L_p$ with nearly tight dimension.
%better dimension than previous bounds, based on Bourgain's embedding.
For any $1 \leq p \leq \infty$ and
any $1 \leq k \leq p$, we give an embedding into $L_p$ with
distortion $O(\lceil \log n/k \rceil)$ in dimension $2^{O(k)}\log
n$.

 Underlying our results is a novel embedding method.
 Probabilistic metric decomposition techniques have
played a central role in the field of finite metric embedding in
recent years. Here we introduce a novel notion of probabilistic
metric decompositions which comes particularly natural in the
context of embedding. Our new methodology provides a \emph{unified
approach} to all known results on embedding of arbitrary metric
spaces. Moreover, as described above, with some additional ideas
they allow to get far stronger results. These metric
decompositions seem of independent interest.\footnote{The paper is
based on the papers \cite{ABN06} and \cite{bartal06}.}