Phase Transitions in the Pooled Data Problem

In this paper, we study the {\em pooled data} problem of identifying the labels associated with a large collection of items, based on a sequence of pooled tests revealing the counts of each label within the pool. In the noiseless setting, we identify an exact asymptotic threshold on the required number of tests with optimal decoding, and prove a {\em phase transition} between complete success and complete failure. In addition, we present a novel {\em noisy} variation of the problem, and provide an information-theoretic framework for characterizing the required number of tests for general random noise models. Our results reveal that noise can make the problem considerably more difficult, with strict increases in the scaling laws even at low noise levels. Finally, we demonstrate similar behavior in an {\em approximate recovery} setting, where a given number of errors is allowed in the decoded labels.

Presented at:
Conference on Neural Information Processing Systems (NIPS), Long Beach, California, December 2017

Note: The status of this file is: Anyone

 Record created 2017-09-05, last modified 2020-07-29

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)