ECCC-Report TR16-021https://eccc.weizmann.ac.il/report/2016/021Comments and Revisions published for TR16-021en-usFri, 19 Feb 2016 08:47:16 +0200
Paper TR16-021
| Noisy Population Recovery from Unknown Noise |
Shachar Lovett,
Jiapeng Zhang
https://eccc.weizmann.ac.il/report/2016/021The 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.
Fri, 19 Feb 2016 08:47:16 +0200https://eccc.weizmann.ac.il/report/2016/021