Information Recovery from Pairwise Measurements

Yuxin Chen, Changho Suh, Andrea J. Goldsmith

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

This paper is concerned with jointly recovering n node variables {xi}{1≤i≤n from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of xi-xj; the observation pattern is represented by a measurement graph G with an edge set E, such that xi-xj is observed if and only if (i,j)∈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 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 minimum channel divergence measures to characterize the degree of measurement corruption, which together with the size of the minimum cut of 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 (n\log n)/(Hel1/2min) for certain information metric Hel1/2min 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 random corruption model, and the haplotype assembly problem. Our theory leads to orderwise tight recovery conditions for all these scenarios.

Original languageEnglish (US)
Article number7544497
Pages (from-to)5881-5905
Number of pages25
JournalIEEE Transactions on Information Theory
Volume62
Issue number10
DOIs
StatePublished - Oct 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Homogeneous graphs
  • Pairwise difference
  • geometric graphs
  • information divergence random graphs

Fingerprint Dive into the research topics of 'Information Recovery from Pairwise Measurements'. Together they form a unique fingerprint.

  • Cite this