b-bit Marginal Regression
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 can be estimated consistently by maximum likelihood by extending [15].
The paper presents a method for b-bit compressive sensing, i.e., estimate x^* from y and A, where y=Q(Ax^*), Q maps a real number into a b-bit string. The algorithm uses the largest entries of A^Ty to estimate x^*/||x^*||. ||x^*|| is estimated using an MLE estimate. The main message of the paper is that two-bit compressive sensing is most efficient in terms of estimating x^* accurately. The overall message seems to be interesting and the empirical results seem to verify it. The paper is well written as well and fun to read. However, the method and the claims of this paper are not rigorous and needs some more work.a) The method just uses one step process of estimating x^* (i.e. uses A^Ty). However, such a method is known to require significantly larger sample complexity and in practice as well the method is significantly worse than the other method like IHT or L1 minimization (authors observe the same in their experiments as well).b) Due to the weak method, the error bounds for the method are also significantly worse than the existing results for compressive sensing (both standard CS and one-bit style CS). For example, the given method naturally cannot do exact recovery even when the measurements are noiseless. Moreover, the recovery is not universal that for each x^*, a new A has to be sampled. This again is not very realistic and interesting scenario to study.c) The claim that b=2-bit CS has the best sample complexity is quite confusing. Because i) the method considered itself is suboptimal (as described above) ii) the analysis of the method gives only an upper bound on samples and authors claim that "inspection of proof indicates that the dependence is tight" is a bit vague and does not imply any lower bound on the number of samples required iii) the analysis of the upper bound as well as MLE estimate of ||x||_* is also not complete and requires computing certain quantities using experiments. Overall the paper contains an interesting claim but the claim is not fully justified. Especially, the method considered to make the claim is quite weak and does not even work well in practice (in reasonably low-noise scenarios).