Information recovery from pairwise measurements: A shannon-theoretic approach

This paper is concerned with jointly recovering n node-variables {x₁,..., x_n} from a collection of pairwise difference measurements. Specifically, several noisy measurements of x_i - x_j are acquired. This is represented by a graph with an edge set ε such that x_i - x_j is observed only if (i, j) ∈ ε. To accommodate the noisy nature of data acquisition in a general way, we model the measurements by a set of channels with given input/output transition measures. Using information-theoretic tools applied to the channel decoding problem, we develop a unified framework to characterize a sufficient and a necessary condition for exact information recovery, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, we isolate and highlight a family of minimum distance measures underlying the channel transition probabilities, which plays a central role in determining the recovery limits. For a broad class of homogeneous graphs, the recovery conditions we derive are tight up to some explicit constant, which depend only on the graph sparsity irrespective of other second-order graph metrics like the spectral gap.