The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Summary
This paper identifies sufficient sample sizes for maximum-likelihood support recovery of sparse binary signals in high-SNR regimes, revealing an information-theoretic threshold and trade-offs between measurement sparsity and computational cost.
View Cached Full Text
Cached at: 09/10/26, 06:12 PM
Paper page - The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Source: https://huggingface.co/papers/2509.01809
Abstract
For sparse binary signals, sufficient sample sizes for maximum-likelihood support recovery are identified in high-SNR regimes, revealing an information-theoretic threshold and trade-offs between measurement sparsity and computational cost, with analysis also covering sparsified dense designs.
We consider the problem ofsupport recoveryforsparse binary signalsfromnoisy linear measurements. Forsparse Gaussian measurement matriceswe identify sufficient conditions on the minimal sample size formaximum-likelihood recoveryin thehigh-SNR regimeds/p to infty, where p denotes the signal dimension, s the number of non-zero components of the signal, and d the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields aninformation-theoretic thresholdof order slog(p/s) / log(ds/p), making explicit the price ofmeasurement sparsity. In particular, we highlight a regime where the sample-complexity loss frommeasurement sparsityis logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originallydense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In theproportional regimes=αp, d=ψp, we prove that, for every fixed target error level δ and every slack varepsilon>0, a sample size of order p/ψ^2 is sufficient forsupport recoveryfor arbitrarily small ψ.
View arXiv pageView PDFAdd to collection
Get this paper in your agent:
hf papers read 2509\.01809
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2509.01809 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2509.01809 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2509.01809 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
Inference Time Context Sparsity: Illusion or Opportunity?
This paper argues that extreme context sparsity is a principled and feasible foundation for LLM inference, showing that current models tolerate up to 100× sparsity without quality loss and that sparse decode kernels can accelerate processing by 10× on existing hardware.
Activation Outliers Matter: Robust Recovery for Quantized Multimodal LLMs
The paper identifies activation quantization as the primary bottleneck in ultra-low-bit quantized multimodal LLMs and proposes ResidualFallbackQuantization (RFQ) to recover performance with minimal overhead.
Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
This paper studies piecewise-stationary low-rank linear contextual bandits, proposes the SPSC algorithm that achieves dynamic regret scaling with the intrinsic rank instead of the ambient dimension, and characterizes the identification boundary for subspace recovery under scalar feedback.
Active Learning for Conditional Generative Compressed Sensing
This paper proposes a framework for conditional generative compressed sensing, proving stable recovery bounds for prompt-conditioned models and demonstrating how prompt matching influences sampling distributions in experiments with Stable Diffusion.
Effects of sparsity and superposition on loss in simple autoencoders
This paper provides a mathematical analysis of superposition in neural networks, deriving upper and lower bounds on L2 reconstruction loss for simple autoencoders with power activation functions, corroborating empirical findings by Elhage et al.