Information recovery from pairwise measurements: A shannon-theoretic approach
Information recovery from pairwise measurements: A shannon-theoretic approach
复制标题
从成对测量中恢复信息：香农理论方法
DOI：
10.1109/isit.2015.7282873
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Goldsmith
中科院分区：
文献类型：
--
作者：
Yuxin Chen;Changho Suh;A. Goldsmith
本文研究从两两差测量集合中联合恢复n个结点变量{x1，…，xn}。具体地说，获得了xi-xj的几个噪声测量。这由具有边集ε的图来表示，使得只有当(i，j)∈ε时才能观察到xi-xj。为了在一般情况下适应数据采集的噪声特性，我们通过一组具有给定输入/输出转换措施的通道来对测量进行建模。利用信息论工具研究信道译码问题，给出了一个统一的框架来刻画精确信息恢复的充要条件，包括一般的图结构、字母表大小和信道转换度量。特别是，我们分离和突出了一族最小距离度量，这是通道转换概率的基础，它在确定恢复极限方面发挥着核心作用。对于一类广泛的齐次图，我们得到的恢复条件紧到某个显式常数，它只依赖于图的稀疏性，而不考虑其他二阶图的度量，如谱间隙。
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.