Mean estimation from adaptive one-bit measurements
Alon Kipnis, John C. Duchi · 2017
We consider the problem of estimating the mean of a normal distribution under the following constraint: the estimator can access only a single bit from each sample from this distribution. We study the squared error risk in this estimation as a function of the number of samples and one-bit measurements n. We consider an adaptive estimation setting where the single-bit sent at step n is a function of both the new sample and the previous n - 1 acquired bits. For this setting, we show that no estimator can attain asymptotic mean squared error smaller than π/(2n)+ O(n-2) times the variance. In other words, one-bit restriction increases the number of samples required for a prescribed accuracy of estimation by a factor of at least π /2 compared to the unrestricted case. In addition, we provide an explicit estimator that attains this asymptotic error, showing that, rather surprisingly, only π /2 times more samples are required in order to attain estimation performance equivalent to the unrestricted case.