ECCC-Report TR14-123https://eccc.weizmann.ac.il/report/2014/123Comments and Revisions published for TR14-123en-usTue, 07 Oct 2014 03:20:09 +0300
Paper TR14-123
| Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions |
Jiapeng Zhang,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2014/123The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of $\eps$. We give an algorithm which solves this problem in time polynomial in $(k^{\log \log k}, n, 1/\eps)$.
This improves on the previous algorithm of Wigderson and Yehudayoff [FOCS 2012] which solves the problem in time polynomial in $(k^{\log k}, n, 1/\eps)$.
Our main technical contribution, which facilitates the algorithm, is a new reverse Bonami-Beckner inequality for the $L_1$ norm of sparse functions.Tue, 07 Oct 2014 03:20:09 +0300https://eccc.weizmann.ac.il/report/2014/123