  We initiate the study of metric embeddings with \emph{outliers}. Given some
metric space $(X,\rho)$ we wish to find a small set of outlier points $K
\subset X$ and either an isometric or a low-distortion embedding of
$(X\setminus K,\rho)$ into some target metric space. This is a natural problem
that captures scenarios where a small fraction of points in the input
corresponds to noise.
  For the case of isometric embeddings we derive polynomial-time approximation
algorithms for minimizing the number of outliers when the target space is an
ultrametric, a tree metric, or constant-dimensional Euclidean space. The
approximation factors are 3, 4 and 2, respectively. For the case of embedding
into an ultrametric or tree metric, we further improve the running time to
$O(n^2)$ for an $n$-point input metric space, which is optimal. We complement
these upper bounds by showing that outlier embedding into ultrametrics, trees,
and $d$-dimensional Euclidean space for any $d\geq 2$ are all NP-hard, as well
as NP-hard to approximate within a factor better than 2 assuming the Unique
Game Conjecture.
  For the case of non-isometries we consider embeddings with small
$\ell_{\infty}$ distortion. We present polynomial-time \emph{bi-criteria}
approximation algorithms. Specifically, given some $\epsilon > 0$, let
$k_\epsilon$ denote the minimum number of outliers required to obtain an
embedding with distortion $\epsilon$. For the case of embedding into
ultrametrics we obtain a polynomial-time algorithm which computes a set of at
most $3k_{\epsilon}$ outliers and an embedding of the remaining points into an
ultrametric with distortion $O(\epsilon \log n)$. For embedding a metric of
unit diameter into constant-dimensional Euclidean space we present a
polynomial-time algorithm which computes a set of at most $2k_{\epsilon}$
outliers and an embedding of the remaining points with distortion
$O(\sqrt{\epsilon})$.
