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

5 Scopus citations

Abstract

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.
Pages2336-2340
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - Sep 28 2015
Externally publishedYes
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
Volume2015-June
ISSN (Print)2157-8095

Other

OtherIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period6/14/156/19/15

All Science Journal Classification (ASJC) codes

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

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

  • Cite this

    Chen, Y., Suh, C., & Goldsmith, A. J. (2015). Information recovery from pairwise measurements: A shannon-theoretic approach. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 2336-2340). [7282873] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282873