Information recovery from pairwise measurements

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

15 Scopus citations


A variety of information processing tasks in practice involve recovering n objects from single-shot graph-based measurements, particularly those taken over the edges of some measurement graph G. This paper concerns the situation where each object takes value over a group of M different values, and where one is interested to recover all these values based on observations of certain pairwise relations over G. The imperfection of measurements presents two major challenges for information recovery: 1) inaccuracy: a (dominant) portion 1 - p of measurements are corrupted; 2) incompleteness: a significant fraction of pairs are unobservable, i.e. G can be highly sparse. Under a natural random outlier model, we characterize the minimax recovery rate, that is, the critical threshold of non-corruption rate p below which exact information recovery is infeasible. This accommodates a very general class of pairwise relations. For various homogeneous random graph models (e.g. Erdos-Rényi random graphs, random geometric graphs, small world graphs), the minimax recovery rate depends almost exclusively on the edge sparsity of the measurement graph G irrespective of other graphical metrics. This fundamental limit decays with the group size M at a square root rate before entering a connectivity-limited regime. Under the Erdos-Rényi random graph, a tractable combinatorial algorithm is proposed to approach the limit for large M (M = nω(1)), while order-optimal recovery is enabled by semidefinite programs in the small M regime.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781479951864
StatePublished - 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

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


Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI

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'. Together they form a unique fingerprint.

Cite this