# Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes

arXiv: https://arxiv.org/abs/2303.00043 · HTML: https://mlsanity.com/paper/2303.00043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 35 references that are in the map.
- First posted on arXiv 28 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [Neural Group Testing to Accelerate Deep Learning](https://mlsanity.com/paper/2011.10704/) (2020)
- [Decoding from Pooled Data: Phase Transitions of Message Passing](https://mlsanity.com/paper/1702.02279/) (2017)
- [Phase Transitions in the Pooled Data Problem](https://mlsanity.com/paper/1710.06766/) (2017)
- [Optimal Nested Test Plan for Combinatorial Quantitative Group Testing](https://mlsanity.com/paper/1407.2283/) (2014)
- [Concentration Inequalities for Bounded Random Vectors](https://mlsanity.com/paper/1309.0003/) (2013)
- [Distributed Reconstruction of Noisy Pooled Data](https://mlsanity.com/paper/2204.07491/) (2022)

## Abstract (arXiv)

In the pooled data problem we are given n agents with hidden state bits, either 0 or 1. The hidden states are unknown and can be seen as the underlying ground truth σ. To uncover that ground truth, we are given a querying method that queries multiple agents at a time. Each query reports the sum of the states of the queried agents. Our goal is to learn the hidden state bits using as few queries as possible. So far, most literature deals with exact reconstruction of all hidden state bits. We study a more relaxed variant in which we allow a small fraction of agents to be classified incorrectly. This becomes particularly relevant in the noisy variant of the pooled data problem where the queries' results are subject to random noise. In this setting, we provide a doubly regular test design that assigns agents to queries. For this design we analyze an approximate reconstruction algorithm that estimates the hidden bits in a greedy fashion. We give a rigorous analysis of the algorithm's performance, its error probability, and its approximation quality. As a main technical novelty, our analysis is uniform in the degree of noise and the sparsity of σ. Finally, simulations back up our theoretical findings and provide strong empirical evidence that our algorithm works well for realistic sample sizes.