On the parallel reconstruction from pooled data

In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal sigmain 0, 1n, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that VertsigmaVert₁= o(n) our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct s with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.

Subjects

Information Theory

Phase Transitions

Pooled Data

Reconstruction

Sparse Signal

DDC Class

004: Informatik

Options

On the parallel reconstruction from pooled data