Information Recovery from Pairwise Measurements

摘要: 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 few observations taking the form $x_{i}-x_{j}$; observation pattern represented by measurement graph $\mathcal{G}$ an edge set $\mathcal{E}$ such that $x_{i}-x_{j}$ observed if and only $(i,j)\in\mathcal{E}$. To account for noisy measurements in general manner, model data acquisition process channels given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, develop \emph{unified} framework characterize fundamental recovery criterion, which accommodates structures, alphabet sizes, In particular, our results isolate family \emph{minimum} \emph{channel divergence measures} degree corruption, together size minimum cut dictates feasibility exact information recovery. For various homogeneous graphs, condition depends almost on sparsity irrespective other graphical metrics; alternatively, sample complexity required these graphs scales like \[ \text{minimum }\asymp\frac{n\log n}{\mathsf{Hel}_{1/2}^{\min}} \] certain metric $\mathsf{Hel}_{1/2}^{\min}$ defined main text, as long not super-polynomial $n$. We apply theory three concrete applications, including stochastic block model, outlier haplotype assembly problem. Our leads order-wise tight conditions all scenarios.