Title: Lossless Prioritized Embeddings.

Author: Michael Elkin and Ofer Neiman 

Abstract: Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X \rightarrow Y$ is said to have a 
{\em prioritized distortion} $\alpha(\cdot)$, for a function $\alpha(\cdot)$, if for any pair $x_j,x'$ of distinct points in $X$, the distortion provided 
by $f$ for this pair is at most $\alpha(j)$. If $Y$ is a normed space, the embedding is said to have {\em prioritized dimension} $\beta(\cdot)$, if $f(x_j)$ 
may have at most $\beta(j)$ nonzero coordinates.

The notion of prioritized embedding was introduced by Filtser and the current authors in \cite{EFN15}, where a rather general methodology  for constructing such 
embeddings was developed. Though this methodology enabled \cite{EFN15} to come up with many prioritized embeddings, it typically incurs some {\em loss} in the 
distortion. In other words, in the worst-case, prioritized embeddings obtained via this methodology incur distortion which is at least a constant factor off, 
compared to the distortion of the classical counterparts of these embeddings. This constant loss is problematic for isometric embeddings. It is also troublesome 
for Matousek's embedding of general metrics into $\ell_\infty$, which for a parameter $k = 1,2,\ldots$, provides distortion $2k-1$ and dimension 
$O(k \log n \cdot n^{1/k})$.

In this paper we devise two {\em lossless} prioritized embeddings. The first one is an {\em isometric prioritized} embedding  of tree metrics into $\ell_\infty$ 
with dimension $O(\log j)$, matching the worst-case guarantee of $O(\log n)$ of the classical embedding of Linial et al. \cite{LLR95}. The second one is a 
prioritized Matousek's embedding of general metrics into $\ell_\infty$, which for a parameter $k=1,2,\ldots$, provides prioritized distortion 
$2 \lceil k {{\log j} \over {\log n}} \rceil - 1$ and dimension $O(k \log n \cdot n^{1/k})$, again matching the worst-case guarantee $2k-1$ in the distortion of 
the classical Matousek's embedding.

We also provide a dimension-prioritized variant of Matousek's embedding. Finally, we devise prioritized embeddings of general metrics into (single) ultra-metric 
and of general graphs into (single) spanning tree with asymptotically optimal distortion.