This paper is concerned with jointly recovering $n$ node-variables $\left\{ x_{ i}\right\}_{ 1\leq i\leq n}$ from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of $x_{ i}-x_{ j}$; the observation pattern is represented by a measurement graph $\mathcal{ G}$ with an edge set $\mathcal{ E}$ such that $x_{ i}-x_{ j}$ is observed if and only if $(i,j)\in\mathcal{ E}$. To account for noisy measurements in a general manner, we model the data acquisition process by a set of channels with given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, we develop a \emph{ unified} framework to characterize the fundamental recovery criterion, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, our results isolate a family of \emph{ minimum} \emph{ channel divergence measures} to characterize the degree of measurement corruption, which together with the size of the minimum cut of $\mathcal{ G}$ dictates the feasibility of exact information recovery. For various homogeneous graphs, the recovery condition depends almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics; alternatively, the minimum sample complexity required for these graphs scales like \[ \text{ minimum sample complexity }\asymp\frac{ n\log n}{ \mathsf{ Hel}_{ 1/2}^{ \min}} \] for certain information metric $\mathsf{ Hel}_{ 1/2}^{ \min}$ defined in the main text, as long as the alphabet size is not super-polynomial in $n$. We apply our general theory to three concrete applications, including the stochastic block model, the outlier model, and the haplotype assembly problem. Our theory leads to order-wise tight recovery conditions for all these scenarios.
Categories: cs.IT cs.DM cs.LG math.IT math.ST stat.ML stat.TH