Decoding from Pooled Data: Information-Theoretic bounds and a Message-Passing Algorithm

Add to your list(s) Download to your calendar using vCal

• Ahmed El Alaoui (UC Berkeley)
• Friday 16 June 2017, 16:00-17:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge..

If you have a question about this talk, please contact Quentin Berthet.

Consider a population consisting of n individuals, each of whom has one of d types (e.g. their blood type, in which case d=4). We are allowed to query this database by specifying a subset of the population, and in response we observe a noiseless histogram (a d-dimensional vector of counts) of types of the pooled individuals. This measurement model arises in practical situations such as pooling of genetic data and may also be motivated by privacy considerations. We study this model in the “random dense” setting where each query involves a random subset of individuals of size proportional to n. We are interested in the number of queries one needs to unambiguously determine the type of each individual, both information-theoretically and in an algorithmically efficient way. We discuss the information-theoretic question and present a message-passing algorithm for recovering the signal from a minimal number of measurements and characterize its exact asymptotic behavior. The analysis reveals a gap between what is statistically possible and what is achieved by our algorithm.

This is joint work with Aaditya Ramdas, Florent Krzakala, Lenka Zdeborova, and Michael Jordan. Preprints: arxiv:1611.09981, arxiv:1702.02279

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.