无损优先嵌入

作者：Michael Elkin,Ofer Neiman

摘要：给定度量空间（X，d）和（Y，ρ）和（X，d）的排序x1，x2，...，xn，嵌入f：X→Y被认为具有优先级失真α（⋅），如果对于X中的任何对xj，x'的不同点，由f对该对提供的失真最多为α（j）。如果Y是一个赋范空间，如果f（xj）可能仅在其第一个β（j）坐标中具有非零项，则认为嵌入具有优先级维度β（⋅）。

优先嵌入的概念由\ cite {EFN15}引入，其中开发了构建这种嵌入的一般方法。虽然这种方法能够引用{EFN15}来提出许多优先嵌入，但它通常会导致失真的一些损失。这种损失对于等距嵌入是有问题的。 Matousek将一般度量嵌入到l∞中也很麻烦，对于参数k = 1,2，...，它提供失真2k-1和维度O（klogn⋅n1/ k）。

在本文中，我们设计了两个无损优先嵌入。第一个是将树度量的等距优先级嵌入到具有维度O（logj）的l∞中。第二个是优先级Matousek将一般度量嵌入到l∞中，它提供优先级失真2⌈klogjlogn⌉-1和维度O（klogn⋅n1/ k），再次匹配最坏情况保证2k-1的失真经典Matousek的嵌入。我们还提供了Matousek嵌入的维度优先级变体。最后，我们将一般度量的优先级嵌入到（单个）超度量和一般图形到具有渐近最优失真的（单个）生成树中。

原文标题：Lossless Prioritized Embeddings

原文摘要：

地址：https://arxiv.org/abs/1907.06983