Information Recovery from Pairwise Measurements

Understand

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 $\mathcal{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 $\mathcal{G}$.
• The imperfection of measurements presents two major challenges for information recovery: 1) $\textit{inaccuracy}$: a (dominant) portion $1-p$ of measurements are corrupted; 2) $\textit{incompleteness}$: a significant fraction of pairs are unobservable, i.e.
• $\mathcal{G}$ can be highly sparse.