# Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements

arXiv: https://arxiv.org/abs/2502.16008 · HTML: https://mlsanity.com/paper/2502.16008/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 21 Feb 2025.

## Builds on (most cited first, 5 of 5)

- [On the sample complexity of parameter estimation in logistic regression with normal design](https://mlsanity.com/paper/2307.04191/) (2023)
- [High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition](https://mlsanity.com/paper/1701.04455/) (2017)
- [Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing](https://mlsanity.com/paper/2207.03427/) (2022)
- [Support Recovery in Universal One-bit Compressed Sensing](https://mlsanity.com/paper/2107.09091/) (2021)
- [Robust 1-bit Compressed Sensing with Iterative Hard Thresholding](https://mlsanity.com/paper/2310.08019/) (2023)

## Built on by (most cited first, 1 of 1)

- [Actively Learning Halfspaces without Synthetic Data](https://mlsanity.com/paper/2509.20848/) (2025)

## Abstract (arXiv)

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.