Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data

Youssef Chaabouni; David Gamarnik

stat.MLMay 11, 2026

Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data

Authors: Youssef Chaabouni, David Gamarnik

Abstract

We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of lower-quality measurements with higher variance. For this heterogeneous-noise setting, we establish sample-size conditions for information-theoretic and algorithmic recovery. On the information-theoretic side, we show that it is sufficient for $(n_1, n_2)$ to satisfy a linear trade-off defining the Price of Quality: the number of low-quality samples needed to replace one high-quality sample. In the agnostic setting, where the decoder is completely agnostic to the quality of the data, it is uniformly bounded, and in particular one high-quality sample is never worth more than two low-quality samples for this sufficient condition to hold. In the informed setting, where the decoder is informed of per-sample variances, the price of quality can grow arbitrarily large. On the algorithmic side, we analyze the LASSO in the agnostic setting and show that the recovery threshold matches the homogeneous-noise case and only depends on the average noise level, revealing a striking robustness of computational recovery to data heterogeneity. Together, these results give the first conditions for sparse recovery with mixed-quality data and expose a fundamental difference between how the information-theoretic and algorithmic thresholds adapt to changes in data quality.

Explore similar work

Sep 1, 2025stat.ML

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

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

s\log(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

ψ

Youssef Chaabouni, David Gamarnik

Sparse Recovery Sparsity Optimal Sample Complexity Noisy Data Sufficient Conditions

Ask PDF

Feb 18, 2026math.ST

Separating Oblivious and Adaptive Models of Variable Selection

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with

\ell_\infty

error guarantees. This variant of the problem is motivated by \emph{variable selection} tasks, where the goal is to estimate the support of a

k

-sparse signal in

\mathbb{R}^d

. Our main contribution is a provable separation between the \emph{oblivious} (for each'') and \emph{adaptive} (for all'') models of

\ell_\infty

sparse recovery. We show that under an oblivious model, the optimal

\ell_\infty

error is attainable in near-linear time with

\approx k\log d

samples, whereas in an adaptive model,

\gtrsim k^2

samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard

\ell_2

setting, where

\approx k \log d

samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with

\approx k\log d

measurements.

Ziyun Chen, Jerry Li, Kevin Tian +1

Sparse Recovery Optimal Sample Complexity

Ask PDF

Oct 28, 2025cs.IT

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on

\mathbf{A}

(e.g., restricted isometry property) guaranteeing unique recovery of

\mathbf{x}^\star

from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

with

\|\mathbf{e}\|_0 \leq q

. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in

\mathbf{A}

can preserve nontrivial information about

\mathbf{x}^\star

under sparse corruption. In this paper, we study what information about

\mathbf{x}^\star

can be \emph{uniformly} recovered from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

for arbitrary

\mathbf{A}\in\mathbb{R}^{m\times n}

and \emph{any}

q

-sparse

\mathbf{e}

. We show that the robust information is precisely

\mathbf{x}^\star + \ker(\mathbf{U})

, where

\mathbf{U}

is the orthogonal projection onto the intersection of rowspaces of all submatrices of

\mathbf{A}

obtained by deleting

2q

rows. This clarifies how the row structure of

\mathbf{A}

governs whether a

q

-sparse corruption allows exact, partial, or only trivial recovery. We further prove every

\mathbf{x}

minimizing

\|\mathbf{y} - \mathbf{A} \mathbf{x}\|_0

belongs to

\mathbf{x}^\star + \ker(\mathbf{U})

, yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.

Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1

Sparse Recovery Adversarial Corruption 3D Gaussian Splatting

Ask PDF