Recovery Of Sparse Binary Vectors From Generalized Linear Measurements

We consider the problem of recovering a sparse binary vector from generalized linear measurements. Our analysis focuses on the linear estimation algorithm introduced by Plan, Vershynin, and Yudovina (2017), alongside information-theoretic lower bounds on the number of measurements required for recovery. These results imply tight sample complexity results for logistic regression and one bit compressed sensing. We also consider the problem of sparse linear regression, where we give tight sample complexity characterisation using a maximum likelihood estimator.