The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

Hugging Face Daily Papers Papers
sparse-recovery support-recovery binary-signals noisy-measurements maximum-likelihood information-theory gaussian-matrices

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.

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime ds/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 an information-theoretic threshold of order slog(p/s) / log(ds/p), making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime s=α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 for support recovery for arbitrarily small ψ.
Original Article
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?

arXiv cs.AI

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.