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

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.

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.

Classical sparse recovery treats all nonzero entries equally, though numerical noise often creates long tails of negligible coefficients. This paper develops an entropy-based notion of effective sparsity to measure the coefficients carrying significant mass. The central quantity, the effective number of nonzeros (ENZ), is obtained by exponentiating the Shannon entropy of the normalized magnitude distribution. We show that ENZ decomposes exactly into the support cardinality multiplied by a distributional efficiency factor, thereby making precise its relation to the $\ell_0$ count and explaining how it discounts uninformative coefficients. Furthermore, the Shannon ENZ is embedded into a parallel Rényi family that recovers several scale-invariant sparsity measures, including the $\ell_1/\ell_2$ ratio, as special cases. We then prove a stability result under a restricted isometry condition, establishing an explicit bound that depends on the tail energy, measurement perturbation, and restricted isometry constant. For computation, a separable unnormalized entropy surrogate is introduced to avoid global coupling. Numerical experiments on sparse signal recovery and gradient-domain image denoising demonstrate that the resulting regularizer is robust, computationally efficient, and competitive with standard sparsity penalties.