论文标题
嘈杂的汇总数据的分布式重建
Distributed Reconstruction of Noisy Pooled Data
论文作者
论文摘要
在汇总的数据问题中，我们得到了一组$ n $的代理，每个代理都有一个隐藏的状态位，$ 0 $或$ 1 $。查询过程返回查询设置查询代理状态的总和。目的是使用尽可能少的查询重建状态。在本文中，我们考虑了汇总数据问题的两个噪声模型。在嘈杂的通道模型中，每个代理的结果都以一定的概率翻转。在嘈杂的查询模型中，每个查询结果都会受到随机高斯噪声的影响。我们的结果是双重的。首先，我们介绍和分析这两个错误模型是一种简单有效的分布式算法，该算法以贪婪的方式重建初始状态。我们的新颖分析降低了误差概率和分布范围，我们的算法以高概率重建了确切的初始状态。其次，我们介绍了算法的仿真结果，并将其性能与近似消息传递（AMP）算法进行比较，这些算法在许多相关问题中猜想是最佳的。
In the pooled data problem we are given a set of $n$ agents, each of which holds a hidden state bit, either $0$ or $1$. A querying procedure returns for a query set the sum of the states of the queried agents. The goal is to reconstruct the states using as few queries as possible. In this paper we consider two noise models for the pooled data problem. In the noisy channel model, the result for each agent flips with a certain probability. In the noisy query model, each query result is subject to random Gaussian noise. Our results are twofold. First, we present and analyze for both error models a simple and efficient distributed algorithm that reconstructs the initial states in a greedy fashion. Our novel analysis pins down the range of error probabilities and distributions for which our algorithm reconstructs the exact initial states with high probability. Secondly, we present simulation results of our algorithm and compare its performance with approximate message passing (AMP) algorithms that are conjectured to be optimal in a number of related problems.
