论文标题
一致的高维圆形以及侧面信息
Consistent High Dimensional Rounding with Side Information
论文作者
论文摘要
在标准舍入，我们希望将每个值的$ x $在大的连续空间（例如$ r $）中映射到离散子集（例如$ z $）的附近点$ p $。从本质上讲，这个过程似乎是不连续的，因为两个连续的嘈杂测量值$ x_1 $和相同值的$ x_2 $彼此之间可能非常接近，但是它们可以四舍五入到不同的点$ p_1 \ ne p_2 $，这在许多应用中是不可取的。在本文中，我们展示了如何使圆形过程完美地连续，从而将任何足够接近的测量值映射到同一点。我们称之为一个一致的过程，并通过允许有关第一个测量的少量信息$ x_1 $单向通信并通过$ x_2 $的圆形过程单上通信并使用。 一致的圆形方案的容错性由一对测量对之间的最大距离定义，这些测量对确保它们始终被舍入到同一点，我们的目标是研究提供的信息量与各种空间的可实现的容错的容量之间的可能权衡。当测量$ x_i $是$ r^d $中的任意向量时，我们表明，通信$ \ log_2（d+1）$的信息既足够且必要（在最坏的情况下），以实现一致的圆形，以达到一些正容忍，当d = 3 = 3时，我们获得了紧密的上和下部的$（0.561+o（0.561+o）（0.561+o）（0.561+o）当我们透露$ \ log_2（k）$的信息时，容忍度有关$ x_1 $的四舍五入。我们通过考虑使用$ k $可用颜色的空间上可能的彩色砖块来分析问题，并使用各种数学技术获取我们的上和下限，包括等距不平等，Brunn-Minkowski定理，Sphere Ackhere Acking Bounds和čeChEchCoomomology。
In standard rounding, we want to map each value $X$ in a large continuous space (e.g., $R$) to a nearby point $P$ from a discrete subset (e.g., $Z$). This process seems to be inherently discontinuous in the sense that two consecutive noisy measurements $X_1$ and $X_2$ of the same value may be extremely close to each other and yet they can be rounded to different points $P_1\ne P_2$, which is undesirable in many applications. In this paper we show how to make the rounding process perfectly continuous in the sense that it maps any pair of sufficiently close measurements to the same point. We call such a process consistent rounding, and make it possible by allowing a small amount of information about the first measurement $X_1$ to be unidirectionally communicated to and used by the rounding process of $X_2$. The fault tolerance of a consistent rounding scheme is defined by the maximum distance between pairs of measurements which guarantees that they are always rounded to the same point, and our goal is to study the possible tradeoffs between the amount of information provided and the achievable fault tolerance for various types of spaces. When the measurements $X_i$ are arbitrary vectors in $R^d$, we show that communicating $\log_2(d+1)$ bits of information is both sufficient and necessary (in the worst case) in order to achieve consistent rounding for some positive fault tolerance, and when d=3 we obtain a tight upper and lower asymptotic bound of $(0.561+o(1))k^{1/3}$ on the achievable fault tolerance when we reveal $\log_2(k)$ bits of information about how $X_1$ was rounded. We analyze the problem by considering the possible colored tilings of the space with $k$ available colors, and obtain our upper and lower bounds with a variety of mathematical techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, and Čech cohomology.
