Part of Advances in Neural Information Processing Systems 28 (NIPS 2015)
Martin Slawski, Ping Li
We consider the problem of sparse signal recovery from m linear measurements quantized to b bits. b-bit Marginal Regression is proposed as recovery algorithm. We study the question of choosing b in the setting of a given budget of bits B=m⋅b and derive a single easy-to-compute expression characterizing the trade-off between m and b. The choice b=1 turns out to be optimal for estimating the unit vector corresponding to the signal for any level of additive Gaussian noise before quantization as well as for adversarial noise. For b≥2, we show that Lloyd-Max quantization constitutes an optimal quantization scheme and that the norm of the signal canbe estimated consistently by maximum likelihood.