Research map / Learning theory and algorithms / Sample complexity
Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes a one-shot top-k correlation (linear estimation) algorithm for exact recovery of k-sparse binary vectors from generalized linear measurements, giving tight sample complexity for noisy 1-bit CS and logistic regression, plus near-matching bounds for sparse binary linear regression.
Problem
Exact recovery of k-sparse binary vectors from noisy linear, one-bit quantized, and logistic (generalized linear) measurements, including sample complexity limits and the conjectured statistical-computational gap for binary sparse linear regression.
Approach
Applies the linear estimation algorithm (average/one-shot correlation with top-k selection) to generalized linear measurements of binary sparse vectors, proves sub-exponential concentration yielding O((k+sigma^2) log n) samples, and pairs it with a Fano-type information lower bound showing this is optimal, removing the conjectured computational gap for 1bCS and logistic regression.
Key results
- Linear estimation recovers k-sparse binary vectors for 1bCS and sparse linear regression with m=O((k+sigma^2) log n) measurements, matching an information-theoretic lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use linear estimation followed by top-k selection for noisy 1-bit measurements | Sparse binary vector recovery · Noisy 1-bit compressed sensing | sample complexity: m=O\inp{\inp{k+\sigma^2}(\log\inp{k}+\log\inp{n-k})} | Helped |
| Use linear estimation followed by top-k selection for logistic regression | Sparse binary vector recovery · Logistic regression | sample complexity: m=O\inp{\inp{k+1/\beta^2}\inp{\log{k}+\log\inp{n-k}}} | Helped |
| Use linear estimation followed by top-k selection for noisy linear measurements | Sparse binary vector recovery · Binary sparse linear regression | sample complexity: m=O\inp{\inp{k+\sigma^2}(\log\inp{k}+\log\inp{n-k})} | Helped |
| Keep only sign information instead of the full noisy linear measurements | Linear estimation + top-k for binary sparse linear regression · Binary sparse linear regression | sample complexity: O((k+\sigma^2)\log{n}) | No clear effect |
| Use linear estimation + top-k rather than lasso | Sparse binary vector recovery · Binary sparse linear regression | computational efficiency | Helped |
| Use linear estimation + top-k rather than the cited general linear-estimation result specialized to binary inputs | Sparse binary vector recovery · Binary sparse linear regression | sample complexity: O(k^2\log\inp{2n/k}) | Helped |
Surprising findings
- Sign-only (1-bit) measurements achieve the same sample complexity order as full-precision noisy linear measurements for sparse binary recovery.
Limitations
- Upper bound analysis for linear estimation is for Gaussian sensing matrices; the lower bound for logistic regression requires Gaussian design.
- Gap between MLE upper and lower bounds in constants; optimality of l=k(1-k/n) not formally proved.
Experimental setup
Metrics: exact recovery probability sample complexity
Baselines: lasso orthogonal matching pursuit maximum likelihood estimator
Builds on: Plan, Vershynin, Yudovina 2017 linear estimation Gamarnik and Zadik binary sparse linear regression lasso
Closest papers by meaning
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.90)
- Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data (ICLR 2026 · similarity 0.89)
- Recovery of sparse linear classifiers from mixture of responses (NeurIPS 2020 · similarity 0.89)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.87)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.86)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.