TY - GEN

T1 - Information recovery from pairwise measurements

AU - Chen, Yuxin

AU - Goldsmith, Andrea J.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84906534114&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906534114&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2014.6875186

DO - 10.1109/ISIT.2014.6875186

M3 - Conference contribution

AN - SCOPUS:84906534114

SN - 9781479951864

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2012

EP - 2016

BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014

Y2 - 29 June 2014 through 4 July 2014

ER -