COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Statistics > Decoding from Pooled Data: Information-Theoretic bounds and a Message-Passing Algorithm

## Decoding from Pooled Data: Information-Theoretic bounds and a Message-Passing AlgorithmAdd 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
- Chris Davis' list
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Guy Emerson's list
- MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
- Machine Learning
- School of Physical Sciences
- Statistical Laboratory info aggregator
- Statistics
- Statistics Group
- bld31
- rp587
Note that ex-directory lists are not shown. |
## Other listsC.U. Ethics in Mathematics Society (CUEiMS) Symposium on Computational Biology Manufacturing Thursdays## Other talksAn intellectual history of the universal basic income Private Statistics and Their Applications to Distributed Learning: Tools and Challenges Molly Geidel: Mid-Century Liberalism and the Development Film Yikes! Why did past-me say he'd give a talk on future discounting? What sort of challenge is climate change? Fifty years of editorialising in ‘Nature’ and ‘Science’ Respiratory Problems |