Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-021 | 11th February 2016 05:34

Noisy Population Recovery from Unknown Noise


Authors: Shachar Lovett, Jiapeng Zhang
Publication: 19th February 2016 08:47
Downloads: 2046


The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped independently with some unknown noise probability, estimate from a few samples the underlying parameters of the model. Previous work designed quasi-polynomial time algorithms which work under the assumption that the noise parameters are exactly known. In this work, we remove this assumption, and show how to recover all the underlying parameters, even when the noise is unknown, in quasi-polynomial time.

ISSN 1433-8092 | Imprint