  We study the design of embeddings into Euclidean space with outliers. Given a
metric space $(X,d)$ and an integer $k$, the goal is to embed all but $k$
points in $X$ (called the ``outliers") into $\ell_2$ with the smallest possible
distortion $c$. Finding the optimal distortion $c$ for a given outlier set size
$k$, or alternately the smallest $k$ for a given target distortion $c$ are both
NP-hard problems. In fact, it is UGC-hard to approximate $k$ to within a factor
smaller than $2$ even when the metric sans outliers is isometrically embeddable
into $\ell_2$. We consider bi-criteria approximations. Our main result is a
polynomial time algorithm that approximates the outlier set size to within an
$O(\log^2 k)$ factor and the distortion to within a constant factor.
  The main technical component in our result is an approach for constructing
Lipschitz extensions of embeddings into Banach spaces (such as $\ell_p$
spaces). We consider a stronger version of Lipschitz extension that we call a
\textit{nested composition of embeddings}: given a low distortion embedding of
a subset $S$ of the metric space $X$, our goal is to extend this embedding to
all of $X$ such that the distortion over $S$ is preserved, whereas the
distortion over the remaining pairs of points in $X$ is bounded by a function
of the size of $X\setminus S$. Prior work on Lipschitz extension considers
settings where the size of $X$ is potentially much larger than that of $S$ and
the expansion bounds depend on $|S|$. In our setting, the set $S$ is nearly all
of $X$ and the remaining set $X\setminus S$, a.k.a. the outliers, is small. We
achieve an expansion bound that is logarithmic in $|X\setminus S|$.
