Information Recovery From Pairwise Measurements

DOI10.1109/TIT.2016.2600566MaRDI QIDQ2976592zbMATH OpenOpenAlexFDO

Authors Yuxin Chen, Changho Suh, Andrea J. Goldsmith

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01369

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

Abstract: This paper is concerned with jointly recovering $n$ node-variables $left{x_{i}ight}_{1leqileqn}$ 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 $mathcalG$ with an edge set $mathcalE$ such that $x_i-x_j$ is observed if and only if $(i,j)inmathcalE$. 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 $mathcalG$ 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 [ ext{minimum sample complexity }asympfrac{nlog 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.

Cited in

(8)

• Random Laplacian matrices and convex relaxations
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Robust group synchronization via cycle-edge message passing
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Recovery of defects from the information at detectors
• Community detection and stochastic block models: recent developments
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Efficient joint object matching via linear programming

This page was built for publication: Information Recovery From Pairwise Measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976592)