Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
Authors: Arya Mazumdar, Neha Sangwan
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 (1b CSbinary), we obtain a sample complexity of O((k + σ2) log n), 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. |
| Researcher Affiliation | Academia | 1Halicio glu Data Science Institute, University of California San Diego, La Jolla, United States. Correspondence to: Neha Sangwan <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Top-k correlated indices Input: Sensing matrix A Rm n and output y Rm Output: a k-sized subset of [1 : n] l (0, . . . , 0), l Rn for each i [1 : n] do li Pm j=1 yj Aj,i end for Sort l in decreasing order and let S be the top k indices. Return: S |
| Open Source Code | No | The paper does not provide any statement about releasing code, nor does it include links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper analyzes a theoretical problem of recovering sparse binary vectors from generalized linear measurements and does not describe or use any specific datasets for experimental evaluation. |
| Dataset Splits | No | The paper does not conduct experiments on specific datasets, therefore, there is no information about dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on mathematical analysis and algorithm design; it does not describe experimental implementations or the hardware used. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical analysis and algorithm design; it does not mention any specific software dependencies or versions used for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on the mathematical analysis of an algorithm's sample and computational complexity; it does not describe an experimental setup with specific hyperparameters or training configurations. |