Research map / Learning theory and algorithms / Matrix and tensor methods
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified 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.
Derives sufficient sample-size conditions for MLE support recovery with sparse Gaussian measurement matrices (price of sparsity) and for recovery after post-hoc sparsification of a dense Gaussian design (price of sparsification), via Chernoff plus union bounds.
Problem
Determining how many samples are needed for exact-ish support recovery of sparse binary signals when the measurement matrix is sparse, or when a dense Gaussian design is sparsified after the fact.
Approach
Shows that the information-theoretic sufficient sample size for sparse Gaussian measurements matches the necessary threshold 2s log(p/s)/log(ds/p) up to constants (so the sample complexity cost is log(s)/log(ds/p)), and extends to sparsified dense designs via a regularized Chernoff parameter that avoids degeneracy in the row MGF.
Key results
- For sparse Gaussian measurements in the high-SNR regime, MLE recovers the support with n >= (1+eps) 2s log(p/s)/log(ds/p), matching the necessary threshold from Wang et al. up to constants.
- For dense Gaussian design sparsified with rate psi=d/p, a sample size of order p/psi^2 suffices for support recovery for sufficiently small psi in the linear sparsity regime.
- Price of sparsity factor is log(s)/log(ds/p); in the example s=p^alpha, d=p^beta the sample-complexity ratio is at most logarithmic while computational gain is nearly linear in p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sparse Gaussian measurements instead of dense Gaussian measurements | MLE support recovery · Sparse measurements, sublinear sparsity, high SNR | sample complexity threshold: \frac{2 s\log(p/s)}{\log s} -> \frac{2 s\log(p/s)}{\log(ds/p)} | Hurt |
| Use sparse Gaussian measurements instead of dense Gaussian measurements | MLE support recovery · Sparse measurements, linear sparsity | sample complexity threshold: \frac{2 h(\alpha) p}{\log{d}} vs. dense threshold \frac{2 h(\alpha) p}{\log{p}} | Hurt |
| Sparsify the dense design and rescale the observations by d/p | MSE minimizer · Active sparsification, linear sparsity and strong sparsification | sample complexity threshold: \Theta\pr{p/\log{p}} -> \Theta\pr{p/\psi^2} | Hurt |
Surprising findings
- Sparsifying measurements in the proportional regime d=Theta(p) makes the price of sparsity negligible.
Limitations
- Sufficiency gives only vanishing fractional Hamming error for the MLE, not exact all-or-nothing recovery; the gap to the necessary condition is not closed in the exact sense.
- MLE is exponential-time, so no polynomial-time algorithm is provided.
- Sparsification result requires psi sufficiently small and the proof uses a shrunken Chernoff parameter with o(1) terms.
Experimental setup
Metrics: support recovery probability symmetric difference fraction
Baselines: Wang et al. necessary conditions Omidiran and Wainwright Lasso threshold
Builds on: Wang et al. necessary conditions for sparse ensembles Reeves et al. dense information-theoretic threshold Gamarnik and Zadik MLE support recovery Omidiran and Wainwright Lasso sparse design
Closest papers by meaning
- Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data (ICLR 2026 · similarity 0.91)
- One-Step Estimator for Permuted Sparse Recovery (ICML 2023 · similarity 0.91)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.90)
- Universality in Learning from Linear Measurements (NeurIPS 2019 · similarity 0.89)
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.88)
- A Fast and Provable Algorithm for Sparse Phase Retrieval (ICLR 2024 · similarity 0.88)
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.