Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements

We consider the problem of exact recovery of a k-sparse binary vector from generalized linear measurements (such as logistic regression). We analyze the linear estimation algorithm (Plan, Vershynin, Yudovina, 2017), and also show information theoretic lower bounds on the number of required measurements. As a consequence of our results, for noisy one bit quantized linear measurements (mathsf1bCSbinary), we obtain a sample complexity of O((k+σ2)logn), where σ2 is the noise variance. This is shown to be optimal due to the information theoretic lower bound. We also obtain tight sample complexity characterization for logistic regression. Since mathsf1bCSbinary is a strictly harder problem than noisy linear measurements (mathsfSparseLinearReg) because of added quantization, the same sample complexity is achievable for mathsfSparseLinearReg. While this sample complexity can be obtained via the popular lasso algorithm, linear estimation is computationally more efficient. Our lower bound holds for any set of measurements for mathsfSparseLinearReg, (similar bound was known for Gaussian measurement matrices) and is closely matched by the maximum-likelihood upper bound. For mathsfSparseLinearReg, it was conjectured in Gamarnik and Zadik, 2017 that there is a statistical-computational gap and the number of measurements should be at least (2k+σ2)logn for efficient algorithms to exist. It is worth noting that our results imply that there is no such statistical-computational gap for mathsf1bCSbinary and logistic regression.