Consistent High Dimensional Rounding with Side Information
share
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 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.
READ FULL TEXT