Information recovery from pairwise measurements: A shannon-theoretic approach

Yuxin Chen, Changho Suh, Andrea J. Goldsmith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


This paper is concerned with jointly recovering n node-variables {x1,⋯, xn} from a collection of pairwise difference measurements. Specifically, several noisy measurements of xi - xj are acquired. This is represented by a graph with an edge set ϵ such that xi - xj 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781467377041
StatePublished - Sep 28 2015
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: Jun 14 2015Jun 19 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


OtherIEEE International Symposium on Information Theory, ISIT 2015
Country/TerritoryHong Kong
CityHong Kong

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Information recovery from pairwise measurements: A shannon-theoretic approach'. Together they form a unique fingerprint.

Cite this