# 稀疏的代价：稀疏与稀疏化测量下稀疏恢复的充分条件 - 来源：HuggingFace Daily Papers（社区热门论文） - 发布时间：2026-09-08 08:00 - AIHOT 分数：34 - AIHOT 链接：https://aihot.news/items/cmtvpqrlf0hj8ronb3w122sqq - 原文链接：https://arxiv.org/abs/2509.01809 ## AI 摘要 研究给出稀疏二值信号在稀疏高斯测量矩阵下支撑恢复的充分条件：高信噪比区间 ds/p→∞ 时，样本量 n 超过 2s·log(p/s)/log(ds/p) 即可让最大似然估计渐近恢复支撑，结合已知下界得到同阶信息论阈值。研究还分析了先由稠密高斯设计生成观测、再用独立稀疏化设计与重缩放响应做估计的情形，在 s=αp、d=ψp 的比例区间内证明样本量约 p/ψ² 即可实现支撑恢复。 ## 正文 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 d​s/p→∞, 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⁡(d​s/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 ε>0, a sample size of order p/ψ2 is sufficient for support recovery for arbitrarily small ψ. Contents 1 Introduction In recent years, sparse signal recovery has gained significant attention, motivated by applications in compressive sensing [8, 2, 5]; signal denoising [3]; sparse regression [16]; data stream computing [4, 13, 17]; combinatorial group testing [6]; etc. Practical examples range from the single-pixel camera, MRI scanners and radar remote-sensing systems to error-correction schemes in digital communications and widely used image-compression formats [8, Chap. 1]. The problem can be formulated as follows. Consider a signal β⋆∈ℝp, unknown but a priori s-sparse for some given s≤p, a random measurement matrix X∈ℝn×p (also referred to as design, features or data) and a noise vector Z∼𝒩⁡(0,σ2​In), where n∈ℕ denotes the sample size and σ2>0 a fixed constant. A vector of observations (also known as labels or annotations) is given by: Y≔X​β⋆+Z. Sparse recovery refers to reconstructing β⋆ given X and Y. Intuitively, this problem can be reduced to recovering the support S⋆ of β⋆, i.e. the set of indices of its non-zero components. In fact, once the support S⋆ is identified, the full signal can be estimated using the corresponding columns of X via the closed-form maximum-likelihood estimator formula βMLE=XS⋆+​Y, where XS⋆+ denotes the Moore-Penrose pseudoinverse of the submatrix formed by the columns of X with indices in S⋆ [12]. Traditionally, X was assumed to be a dense random matrix with sub-Gaussian entries. Previous works have shown that the complexity of the problem in terms of required sample size exhibits two phase transitions at two thresholds nINFnALG: polynomial-time recovery. Wainwright [21] shows that if n≥(1+ε)​nALG then the Lasso [20], which is a polynomial-time algorithm, succeeds in recovering the support of β⋆. 1.1 Sparse measurement setting While dense matrices offer an optimal sample size, they are costly in terms of storage and computation. Sparse measurement matrices, where the number of non-zero entries per measurement vector scales significantly smaller than the signal dimension, mitigate these costs: they require significantly less storage and allow for more efficient computations, as matrix-vector multiplications and incremental updates can be performed faster. In addition, they enable efficient signal recovery algorithms by taking advantage of the structural properties of the problem [10]. However, this sparsity comes at the cost of increased sampling complexity [22]. This raises the following key question: How does measurement sparsity trade off with sampling complexity? Some of the prior studies have explored this sparse measurement setting. Wang et al. [22] establish necessary conditions for sparse recovery for various measurement sparsity regimes. Let d denote the expected number of non-zero components of a row of X. Their work reveals three regimes of behavior depending on d​s/p, the expected number of non-zero components of β⋆ that align with non-zero components of a row of X. The three regimes are: d​s/p→+∞, d​s/p=τ for some constant τ>0, and d​s/p→0. They show that in each regime, the number of samples n must exceed a specific information-theoretic lower bound for any algorithm to reliably recover the signal’s support. In particular, in the first regime, when d​s/p→+∞, the necessary condition threshold of [22] is the same as the one of the dense case, while it increases dramatically in the third regime, where d​s/p→0. They work with entries rescaled so that Var⁡(X​β⋆) matches the dense case, while we keep Var⁡(Xi​j)=1. The settings are equivalent since any scaling of X can be accounted for in β⋆. In this work, we examine the opposite question: how many samples are enough to guarantee a reliable recovery? For simplicity, we assume the signal is binary, i.e. β⋆∈{0,1}p. Note that in this case, recovering the support is equivalent to recovering the signal. This assumption is very common in the literature [1, 19, 9]. Intuitively, detecting a component of size 1 is at least as hard as detecting a stronger component, so the resulting thresholds are representative of signals with non-zero entries bounded away from zero by 1, i.e. β⋆∈{β∈ℝp:‖β‖0=s and minj∈[p]:βj≠0|βj|≥1}. Our first main result (Theorem 1) states that in the high signal-to-noise ratio (SNR) regime where d​s/p→+∞, if the number of samples n is larger than a threshold given by: nINFSP=2​s​log⁡(p/s)log⁡(d​s/p), (1) then the MLE asymptotically recovers the support of the signal. The proof uses a Chernoff bound on the mean-squared-error difference between a competing support and the true one, followed by a union bound over supports. The sharpness of the threshold (1) follows from a tight asymptotic analysis of the row moment generating function, which exploits the conditional Gaussianity of measurement rows given the random sparsity pattern of their entries. Bringing our result together with the necessary condition shown by Wang et al. [22], we reveal that the problem exhibits a phase transition – similar to the one known in the dense case – at the information-theoretic threshold nINFSP. In particular, if there exists a constant ε>0 such that n≤(1−ε)​nINFSP then it is information-theoretically impossible to ensure a reliable recovery of the support of the signal, and if there exists a constant ε>0 such that n≥(1+ε)​nINFSP then the MLE ensures a reliable recovery of the support. Our findings therefore answer the question of exactly how much data is needed for recovery. However, the two bounds refer to different notions of recovery: the necessity statement negates exact support recovery uniformly over signals, whereas our sufficiency statement establishes only vanishing fractional Hamming error in probability for the MLE; we discuss this gap in Remark 2.1. We call the amount of additional observations in the sparse setting compared to the dense one price of sparsity. Precisely, restricting each measurement to d non-zeros inflates the required sample size by a factor of Γ=log⁡s/log⁡(d​s/p), quantifying the sampling complexity vs. measurement sparsity trade-off. In particular, we note that in the proportional regime s=Θ⁡(p), d=Θ⁡(p), this factor becomes negligible. Regarding the computational complexity, Omidiran and Wainwright [18] show that the Lasso performs as well in the sparse setting as in the dense setting, assuming a slow decay of sparsity. They show that, under some slow sparsity assumption, it is sufficient for the sample size n to be larger than the algorithmic threshold of the dense setting discussed above, given by: nALG=2​s​log⁡(p−s), specifically for the Lasso to ensure a reliable polynomial time recovery of β⋆. Although the sparsity assumption under which this result holds allows for the density rate d/p to go to 0 as p→+∞, it still doesn’t allow the measurements to be very sparse. In fact, it requires that: d/p=ω(s−1/3)andd/p=ω((log⁡log⁡(p−s)log⁡(p−s))1/3). (2) This raises a question about what happens in a sparser regime. Although our work does not address algorithmic questions, our sufficiency result extends to a strictly broader sparsity regime than (2), leaving open the possibility of corresponding polynomial-time improvements in this regime. 1.2 Active Sparsification The applications of the signal recovery problem [8, Chapter 1] considered in this paper can be broadly categorized into two classes: - Applications where X is designed, e.g. involving signal compression and reconstruction. - Applications where X is observed, e.g. sparse regression, signal denoising, and error correction. In light of this categorization, we note that measuring the trade-off between measurement sparsity and sampling complexity is particularly useful for the first class of problems. It provides practitioners with an exact description of how the measurement matrix should be designed, in terms of size and sparsity, to optimize the computational cost of signal recovery. However, this is rendered useless in the second class of problems when the measurement matrix is observed and dense. This motivates the second key question: given an initially dense measurement matrix, is there a way to make it sparse and still aim to recover the original signal? The question of whether a dense object can be substantially sparsified post-hoc without compromising a downstream task also arises in the neural network compression literature, going back to the Optimal Brain Damage (OBD) framework of LeCun, Denker and Solla [14] and its second-order refinement, Optimal Brain Surgeon (OBS) of Hassibi and Stork [11]: there, one asks whether a trained network’s weights can be largely zeroed out with little loss in predictive performance, and recent theoretical work has obtained post-training pruning guarantees for wide multilayer perceptrons [7]. The object being sparsified differs (estimator parameters there, the measurement matrix here) but the post-hoc sparsification question is shared. Concretely, we model sparsification as follows. Given a dense Gaussian design X, we form a sparsified design X~ by setting each entry of X to zero independently with probability 1−d/p, keeping it unchanged otherwise. Equivalently, X~i​j≔Bi​j​Xi​j where Bi​j,i∈[n],j∈[p] are i.i.d. Ber​(d/p) random variables independent of X, and d≤p controls the sparsification rate. The dense observations Y=X​β⋆+Z are then rescaled accordingly to form Y~≔(d/p)​Y, and recovery is attempted from (X~,Y~). This setting, in which the observations are generated with a dense measurement matrix, but the signal is recovered using a sparsified version of it, is closely related to the “missing covariates” or “missing-at-random” framework studied in high-dimensional statistics. Prior work by Loh and Wainwright [15], established algorithmic ℓ2-error bounds for regression under this model, assuming dense Gaussian designs and a constant missingness rate. Our analysis in Section 3 complements this line of research by focusing instead on information-theoretic support-recovery thresholds and deriving the precise sample complexity cost incurred by sparsification in this regime. In our examination of the sparsification question, we focus on the linear sparsity and strong linear sparsification regime where s=α​p and d=ψ​p, with α∈(0,1) fixed and ψ>0 fixed and sufficiently small. Specifically, our second main result (Theorem 3) states that, for every fixed error tolerance δ∈(0,1) and every slack ε>0, there exists ψ0=ψ0​(α,δ,ε)>0 such that, for every fixed ψ∈(0,ψ0), a sample size n larger than the threshold 2​h​(α)​plog⁡(1+δ​ψ2(1−ψ)​(2−δ⁡(1−ψ))) (3) suffices for the minimizer of the mean squared error (MSE) based on the sparsified measurements and accordingly-rescaled observations to recover the true support up to error fraction δ. The proof of Theorem 3 is substantially more involved than that of Theorem 1 because the rescaled observations Y~ are a rescaling of the original observations Y, not a noisy projection of the true signal through the sparsified design X~. As a consequence, the row moment generating function arising in the Chernoff bound depends on the realization of the random sparsification mask, and the most natural choice of Chernoff parameter introduces a degeneracy on an exponentially small set of masks that, treated directly, would force the analysis through an unverified uniform-integrability hypothesis. We resolve this by evaluating the Chernoff bound at a shrunken Chernoff parameter: a regularized choice that removes the degeneracy uniformly over masks at the cost of a controlled slack in the sample-complexity bound, which the assumption n≥(1+ε)​nSP⋆ absorbs. The smallness condition on ψ is precisely the cost of this regularization, not a claim that larger ψ is intrinsically harder. We believe this regularized Chernoff parameter device is of independent methodological interest. In the strong-sparsification regime where ψ→0, the sufficient threshold (3) effectively writes: nINFSP=Θ⁡(pψ2). (4) We call the amount of additional observations in the sparsification setting compared to the dense one price of sparsification. Unlike the price of sparsity, it is not due to the sparsity of the measurements but rather to a bias in the observations. We also interpret our result as providing an expression of the sparsification budget: the level up to which one could sparsify their data and still recover the true signal. Inverting the sample-complexity bound (3), in the regime n=Ω⁡(p), recovery upon active sparsification holds as long as ψ≥c​p/n, for some constant c>0. Explicitly: a practitioner with n observations may zero out all but an order-p/n fraction of the design’s entries (on average, per row) and still recover the signal. Consequently, doubling the sample size buys an additional factor of 2 in terms of sparsification budget. 1.3 Use of large language models During the development of this work, the authors used large language models (Anthropic’s Claude Opus 4.7) as a discussion partner for some of the technical development. In particular, the idea of evaluating the Chernoff bound at the shrunken parameter θp,λ=λ​θ⋆ for λ∈(0,1), which underlies Lemma 5.2 and is the technical device that eliminates the uniform-integrability hypothesis present in the conference version, emerged from such discussions. All mathematical statements have been fully verified by the authors, who take sole responsibility for the correctness of the paper. 1.4 Outline and Notations We organize the rest of the paper as follows. Section 2 studies the sparse measurement setting. Section 3 examines recovery after sparsifying an originally dense measurement matrix. Section 4 contains the proofs of Theorem 1 and Corollary 2. Section 5 contains the proof of Theorem 3. Section 6 concludes and sketches future work directions. Throughout this document, we will use the following notations. We denote by h⁡(⋅) the binary entropy: h⁡(x)=−x​log⁡x−(1−x)​log⁡(1−x), x∈(0,1). We call ℓ0-norm the number of non-zero coordinates of x∈ℝd, that is ‖x‖0≔∑i=1d𝟙​(xi≠0). We call support of u∈ℝp the set of indices of the non-zero components of u and denote it Supp​(u)≔{i∈[p]:ui≠0}, so that |Supp​(u)|=‖u‖0. We call symmetric difference between two sets S1 and S2 the set of elements in one but not the other and denote it S1​△​S2≔(S1∪S2)∖(S1∩S2). 2 Sparse Recovery using Sparse Measurements 2.1 Setting Let n,p,s,d∈ℕ such that d,s≤p. We define a sparse Gaussian matrix in ℝn×p as follows. Definition 2.1 (Sparse Gaussian matrix). We call X=[Xi​j]i∈[n],j∈[p]∈ℝn×p a sparse Gaussian matrix with parameter d if for all i∈[n],j∈[p] we have: Xi​j=Bi​j​Ni​j, where (Bi​j)i∈[n],j∈[p]∼i.i.d.Ber​(d/p) and (Ni​j)i∈[n],j∈[p]∼i.i.d.𝒩⁡(0,1) are mutually independent, Gaussian random variables. Note that d is the expected number of non-zero components per row of X. In our setting, we assume d to be of smaller order of magnitude than p, i.e. d=o⁡(p). Let X be a sparse Gaussian random matrix of parameter d, and Z be a random vector in ℝn such that Z∼𝒩⁡(0,σ2​In), with σ>0 a fixed constant. Let β⋆∈{0,1}p be a deterministic vector such that ‖β⋆‖0=s. We define the random vector Y as: Y≔X​β⋆+Z. (5) Of particular interest is the signal-to-noise ratio (SNR), known to be an important quantity for characterizing the difficulty of sparse recovery problems [22, 19]. It’s defined as follows: SNR≔𝔼​‖X​β⋆‖22𝔼​‖Z‖22=d​sp​σ2. (6) The maximum likelihood estimator (MLE) of β⋆ is defined by the random vector: β^≔argminβ∈{0,1}p,‖β‖0=s‖Y−X​β‖22. (7) We are interested in the minimum number of samples n required so that the MLE (7) asymptotically recovers the true signal β⋆. Specifically: given an error tolerance δ∈(0,1), we wish to determine the minimum number of samples n as a function of p, s and d required so that: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)⟶1,as ​n,p,s,d→+∞. 2.2 Results Our first main result, Theorem 1, provides a sufficient condition on the sample size for reliable support recovery when using sparse measurements. Theorem 1 (Sufficient conditions for sparse recovery using sparse measurement matrices). Suppose p,s,d→+∞, d=o⁡(p) and d​s=ω⁡(p) (i.e. SNR→+∞). Let δ∈(0,1). We consider two different regimes. Assume s=o⁡(p). Let nSP⋆≔2​s​log⁡(p/s)log⁡(d​s/p)+log⁡(δ/(2​σ2)). If there exists ε>0 such that n≥(1+ε)​nSP⋆, then the MLE β^ recovers β⋆ up to error δ w.h.p.: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)≥1−exp⁡(−ε​s​log⁡(p/s)+o⁡(s​log⁡(p/s))), as n,p,s,d→+∞. Assume there exists a constant α∈(0,1) such that s=α​p. Let: nSP⋆≔2​h​(α)​plog⁡d+log⁡(δ​α/(2​σ2)), where h⁡(⋅) denote the entropy function. If there exists ε>0 such that n≥(1+ε)​nSP⋆, then the MLE β^ recovers β⋆ up to error δ w.h.p.: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)≥1−exp⁡(−ε​h​(α)​p+o⁡(p)), as n,p,s,d→+∞. The proof of Theorem 1, given in section 4.1, uses large deviation techniques to bound the probability of a high-error support to have a lower MSE than the true one, then a union bound over such supports. We give below a brief proof sketch of Theorem 1. Let 𝒮 denote the set of supports of cardinality s and S⋆=Supp​(β⋆). For any S∈𝒮, we denote by 𝟙S the vector in {0,1}p such that [𝟙S]i=𝟙​(i∈S) for all i∈[p]. We define the loss function L over 𝒮 such that L⁡(S)≔‖Y−X​𝟙S‖22, so that Supp​(β^)=argminS∈𝒮L​(S). As p gets large, the event “L⁡(S)0 such that n≤(1−ε)​nINFSP then, as n,p,s,d→+∞, there exists no decoder g:ℝn→{β∈{0,1}p:‖β‖0=s} such that: maxβ⋆∈{0,1}p,‖β⋆‖0=s⁡ℙX,Z​(g⁡(Y)≠Supp​(β⋆))→0. In this sense, it is information-theoretically impossible to ensure an asymptotically reliable recovery. (ii) If there exists ε>0 such that n≥(1+ε)​nINFSP, then as n,p,s,d→+∞: |Supp​(β^)​△​Supp​(β⋆)|2​s⟶0, in probability. In this sense, the MLE (7) ensures an asymptotically reliable recovery. The proof of Corollary 2 is given in section 4.2. Statement (i) is due to Wang et al. [22], while statement (ii) follows from Theorem 1 and is the main contribution of this section. Remark 2.1 (Limitations). Statements (i) and (ii) refer to different notions of recovery: (i), due to [22], negates exact support recovery uniformly over signals, while (ii) only establishes vanishing fractional Hamming error in probability for the MLE. The two are logically compatible, so Corollary 2 establishes a phase transition weaker than the All-or-Nothing phenomenon of Reeves, Xu and Zadik [19], who in the dense setting state both bounds in terms of the same quantity. We believe an analogous All-or-Nothing strengthening should hold in our setting but leave it to future work. We interpret Theorem 1 and Corollary 2 as follows. Phase transition. For simplicity, we only discuss the sublinear sparsity regime, defined by s=o⁡(p). Previous works on sparse recovery in the dense case ([19],[9]) have shown the existence of an information-theoretic threshold: nINF=2​s​log⁡(p/s)log⁡s, (8) at which the complexity of support recovery in terms of sample size exhibits a phase transition, where the recovery of any fraction of the support is impossible for n≤(1−ε)​nINF, and full recovery is guaranteed by the MLE for n≥(1+ε)​nINF. In light of this, we ask if the support recovery problem for the class of sparse measurement matrices described above exhibits a similar behavior. In Corollary 2, we show that indeed, it exhibits a similar phase transition at an information-theoretic threshold given by: nINFSP=2​s​log⁡(p/s)log⁡(d​s/p). (9) In Table 1, we summarize these information-theoretic thresholds alongside known algorithmic thresholds for the sublinear sparsity regime (s=o⁡(p)), highlighting the comparison between dense and sparse measurements in the high-SNR setting. 媒体内容 · 前往原文查看 Table 1: Comparison of Sample Complexity Thresholds for Sublinear Sparsity (s=o⁡(p)). Info-Theoretic Algorithmic Measurement Necessary Sufficient Necessary Sufficient Dense 2​s​log⁡(p/s)log⁡s [19, 22] 2​s​log⁡(p/s)log⁡s [9, 19] 2​s​log⁡(p−s) [9] 2​s​log⁡(p−s) [21] Sparse, high SNR 2​s​log⁡(p/s)log⁡(d​s/p) [22] 2​s​log⁡(p/s)log⁡(d​s/p) (Thm 1) Unknown 2​s​log⁡(p−s) [18]† †Holds under the slow decay of sparsity assumption in [18], see (2). Price of Sparsity. In particular, we notice that nINFSP≥nINF. This confirms the intuition that sparse recovery requires more samples in the sparse measurement case. Corollary 2 is to be interpreted as providing an exact value for the price of sparsity, i.e. the extra amount of observations required in the sparse setting compared to the dense one, which is given by: Γ≔nINFSPnINF=log⁡slog⁡(d​s/p)>1. (10) Note that the expression of the price of sparsity heavily depends on the regimes of d and s. The smaller the density rate d/p, the more “expensive” the desired sparsity of the measurements is, as suggested by the expression of Γ. In particular, Γ could take any value in (1,+∞), depending on the regimes of d and s w.r.t. p. Example 2.1. Consider the setting where s=pα, d=pβ with α,β∈(0,1) such that α+β>1. Then Γ=α/(α+β−1)∈(1,+∞), which approaches 1 when β approaches 1 (low measurement sparsity), and approaches +∞ when α is fixed and β approaches 1−α (high measurement sparsity). Thus, we see a measurement sparsity vs. sampling complexity trade-off, which can also be interpreted as a trade-off between sampling complexity and computational cost. We consider an example that highlights this trade-off. Example 2.2. Let φ⁡(x)≔x/log⁡x for x≥e. Consider two measurement matrices: X1 a dense Gaussian in ℝn1×p and X2 a sparse Gaussian ℝn2×p with only d=min⁡(po⁡(1),φ−1​(o⁡(φ⁡(p)))) expected non-zero entries per row; and an s-sparse signal β⋆∈ℝp, in the linear sparsity regime where s=α​p for constant α∈(0,1). On the one hand, the number of samples required for reliable recovery raises from n1=nINF=Θ⁡(p/log⁡p) in the dense case to n2=nINFSP=Θ⁡(p/log⁡d) in the sparse one. On the other hand the computational cost of recovery the support is smaller in the sparse case, as matrix-vector multiplication cost drops from n1​p=Θ⁡(p2/log⁡p) to n2​d=Θ⁡(p​d/log⁡d). This highlights a trade-off between sampling complexity and computational cost. Namely, the sample-complexity ratio n2/n1 is at most logarithmic in p, while the computational gain n1​p/(n2​d) is nearly linear in p. Proofs of these statements are given in section 4.3. Allowing for more sparsity. Note that the sparsity assumption under which Theorem 1 guarantees reliable recovery is weaker than the sparsity assumption of the sufficient algorithmic threshold of Omidiran and Wainwright [18] which guarantees polynomial-time recovery if there exists ε>0 such that n≥(1+ε)​nALG. As they show, this holds under the assumption that: (dp)3​min⁡{s,log⁡log⁡(p−s)log⁡(p−s)}→+∞. For example, when s=Θ⁡(p), this requires that d=ω⁡(p2/3), while our result holds under the weaker assumption of d=ω⁡(1). Equivalently, our information-theoretic guarantee tolerates measurements whose number of non-zero entries per row grows arbitrarily slowly with p, whereas [18] requires this number to grow polynomially. This broader sparsity regime comes at the cost of potential super-polynomial computational complexity, since computing the MLE (7) is exponential-time in general. 3 Sparse Recovery via Active Sparsification 3.1 Setting Let n,p,s,d∈ℕ and β⋆∈{0,1}p s-sparse, defined as in Section 2.1. Let X∈ℝn×p such that (Xi,j)i∈[n],j∈[p]∼i.i.d.𝒩⁡(0,1) and Z∼𝒩⁡(0,σ2​In), with σ>0 constant. Let Y≔X​β⋆+Z∈ℝn. Let (Bi​j)i∈[n],j∈[p]∼i.i.d.Ber​(d/p). We define the following sparsified version of X: X~∈ℝn×p​such that​X~i​j≔Bi​j​Xi​j,∀i∈[n],j∈[p]. (11) In addition, we define a rescaled version of Y as follows: Y~≔dp​Y∈ℝn. (12) An estimator of β⋆ is defined by the random vector: β^≔argminβ∈{0,1}p,‖β‖0=s‖Y~−X~​β‖22. (13) That is, the observations are generated with a dense measurement matrix (X), but the signal is recovered using a sparsification of that matrix (X~). We formalize the problem we address below as follows: given an error tolerance δ∈(0,1), we wish to determine the minimum number of samples n in terms of p, s and d required so that: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)⟶1,as ​n,p,s,d→+∞. 3.2 Results Our second main result, Theorem 3, provides a sufficient condition on the sample size for reliable support recovery after sparsifying an originally dense measurement matrix. Theorem 3 (Sufficient conditions for sparse recovery using sparsified measurements). Fix α,δ∈(0,1). For every ε>0, there exists ψ0=ψ0​(α,δ,ε)>0 such that the following holds. Let ψ∈(0,ψ0) be fixed, and suppose that, as p→∞, s=α​p and d=ψ​p, up to harmless integer rounding. Let nSP⋆≔2​h​(α)​plog⁡(1+δ​ψ2(1−ψ)​(2−δ⁡(1−ψ))). (14) If n≥(1+ε)​nSP⋆, then β^ recovers β⋆ up to error δ w.h.p.: ℙ⁡(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)⟶1. The proof of Theorem 3 is given in Section 5. It follows the same Chernoff-plus-union-bound outline as Theorem 1, with the substantial difference that the row moment generating function now depends on the realization of the sparsification mask; the technical core is a regularized Chernoff parameter device that sidesteps a vanishing-discriminant defect, sketched in detail at the start of Section 5. We interpret Theorem 3 as follows. Arbitrary sparsification rate. According to Theorem 3, for every fixed target accuracy and slack, support recovery is possible for all sufficiently small fixed ψ, provided a large enough sample size. Strong-sparsification regime. In the strong-sparsification regime where ψ→0, the denominator of nSP⋆ in (14) is effectively δ​ψ2/(2−δ), and hence the sufficient condition upper bound writes: nINFSP=2​(2−δ)​h​(α)​pδ​ψ2=Θ⁡(pψ2). (15) Price of Sparsification. We interpret our result as providing a value for the price of sparsification, i.e. the extra amount of observations required due to the information loss resulting from sparsification. In the linear sparsity and strong-sparsification regime, it writes: ΓSparsification≔nINFSPnINF=Θ⁡(p/ψ2)Θ⁡(p/log⁡p)=Θ⁡(log⁡pψ2). Unlike the intrinsically-sparse-observations setting studied in Section 2, this extra amount of required observations is not due to the sparsity of the measurements. In fact, one can check from (10) that in the proportional sparsity regime where d=Θ⁡(p), the price of sparsity is negligible, i.e. Γ→1. Instead, the price of sparsification is due to a bias in the observations that we explain by the fact that the sparsified observations Y~ were not obtained as noisy projections of the true signal as in the original model (5), but rather via a naïve rescaling of the original observations (12). By simply rescaling the observations we did not discard the information in Y coming from the nullified components of X, hence introducing a bias. Sparsification budget. Given dense data and a fixed large enough sample size n, by up to how much could we sparsify the data and still get recovery? We call this the sparsification budget. According to our result (15), its expression in the strong-sparsification regime is given by: ψbudget=Θ⁡(p/n). In particular, the above expression only makes sense when n=Ω⁡(p), below which Theorem 3 does not hold. 4 Sparse Recovery using Sparse Measurements: Proofs 4.1 Proof of Theorem 1 For any i∈[n], we denote by Xi≔(Xi​j)j∈[p], Bi≔(Bi​j)j∈[p], Ni≔(Ni​j)j∈[p]. We denote by S⋆≔Supp​(β⋆) the support of β⋆. Let 𝒮≔{S⊂[p]:|S|=s}. We define the function: L: 𝒮⟶[0,+∞) S⟼‖Y−X​𝟙S‖22, where 𝟙S denotes the vector in {0,1}p such that [𝟙S]j=𝟙​(j∈S) for all j∈[p]. Note that, since X and Y are random, L⁡(S) is a random variable for every S∈𝒮. In addition, note that: L⁡(S)=‖Z‖22+‖X⁡(𝟙S⋆−𝟙S)‖22+2​⟨Z,X⁡(𝟙S⋆−𝟙S)⟩∀S∈𝒮, and, in particular: L⁡(S⋆)=‖Z‖22=∑i=1nZi2. Fix S∈𝒮 such that M≔|S​△​S⋆|/2≥δ​s, and let U≔S⋆∖S, V≔S∖S⋆. Note that |U|=|V|=M. We define: Δ≔L⁡(S)−L⁡(S⋆). Proposition 4.1. As n,p,s,d→+∞: ℙ⁡(Δ≤0)≤(2​σ2​pδ​d​s)n/2​eo⁡(n). Proof. See section 4.1.3. Hence, we obtain: ℙ⁡(‖Y−X​𝟙S‖22≤‖Y−X​𝟙S⋆‖22)≤(2​σ2​pδ​d​s)n/2​eo⁡(n), (16) for any S∈{0,1}p such that |S|=s and |S​△​S⋆|≥2​δ​s. Using (16) and the union bound over the set of supports S​ s.t. ​|S​△​S⋆|≥2​δ​s, we obtain: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s) ≥ℙX,Z(‖Y−X𝟙S‖22>‖Y−X𝟙S⋆‖22,∀S:|S△S⋆|≥2δs) =1−ℙX,Z(∃S:|S△S⋆|≥2δs,‖Y−X𝟙S‖22≤‖Y−X𝟙S⋆‖22) ≥U.B.1−∑S:|S​△​S⋆|≥2​δ​sℙX,Z(‖Y−X𝟙S‖22≤‖Y−X𝟙S⋆‖22) ≥1−(ps)​(2​σ2​pδ​d​s)n/2​eo⁡(n). 4.1.1 Sublinear regime: s=o⁡(p) Using the Corollary of Stirling: log⁡(ps)=s​log⁡(p/s)​(1+o⁡(1)), in the RHS of the inequality above, we obtain: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s) ≥1−exp⁡[s​log⁡(p/s)​(1+o⁡(1))−n2​(log⁡(δ​d​s2​σ2​p)+o⁡(1))]. Let nSP⋆≔2​s​log⁡(p/s)log⁡(d​s/p)+log⁡(δ/(2​σ2)). Then if n≥(1+ε)​nSP⋆ for some constant ε>0, we have: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s) ≥1−exp⁡[s​log⁡(p/s)​(1+o⁡(1))−(1+ε)​nSP⋆2​(log⁡(δ​d​s2​σ2​p)+o⁡(1))] =1−exp⁡[s​log⁡(p/s)​(−ε+o⁡(1)−1+εlog⁡(d​s/p)+log⁡(δ/(2​σ2))​o​(1))] =1−exp⁡(s​log⁡(p/s)​(−ε+o⁡(1))). Hence, as n,p,s,d→+∞: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)≥1−exp⁡(−ε​s​log⁡(p/s)+o⁡(s​log⁡(p/s)))⟶1. 4.1.2 Linear regime: s=α​p , α∈(0,1) Using the Corollary of Stirling: log⁡(ps)=p​h​(α)​(1+o⁡(1)), we get: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s) ≥1−exp⁡[p​h​(α)​(1+o⁡(1))−n2​(log⁡(δ​d​s2​σ2​p)+o⁡(1))]. Similarly to above, we take nSP⋆≔2​h​(α)​plog⁡d+log⁡(δ​α/(2​σ2)). If n≥(1+ε)​nSP⋆ for some constant ε>0, then we obtain, as p,s,d→+∞: ℙX,Z​(|Supp​(β⋆)​△​Supp​(β^)|<2​δ​s)≥1−exp⁡(−ε​h​(α)​p+o⁡(p))⟶1, concluding the proof. ∎ 4.1.3 Proof of Proposition 4.1 We have: Δ ≔L⁡(S)−L⁡(S⋆) =‖X⁡(𝟙S⋆−𝟙S)‖22+2​⟨Z,X⁡(𝟙S⋆−𝟙S)⟩ =∑i=1n⟨Xi,𝟙S⋆−𝟙S⟩2+2​∑i=1nZi​⟨Xi,𝟙S⋆−𝟙S⟩. We denote by (Δi)i∈[n] the terms of the sum in the above expression, that is: Δi≔⟨Xi,𝟙S⋆−𝟙S⟩2+2​Zi​⟨Xi,𝟙S⋆−𝟙S⟩. Note that (Δi)i∈[n] are i.i.d. and Δ=∑i=1nΔi. Now using the Chernoff bound: ℙ⁡(Δ≤0)=ℙ⁡(−Δ≥0)=infθ≥0ℙ⁡(e−θ​Δ≥1)≤infθ≥0M−Δi​(θ)n. (17) We now study the moment generating function of −Δi, i.e. M−Δi​(⋅). We have: M−Δi​(θ) =𝔼Xi,Zi​[e−θ⁡[⟨Xi,𝟙S⋆−𝟙S⟩2+2​Zi​⟨Xi,𝟙S⋆−𝟙S⟩]] =𝔼Xi​[e−θ​⟨Xi,𝟙S⋆−𝟙S⟩2​𝔼Zi​[e−2​θ​Zi​⟨Xi,𝟙S⋆−𝟙S⟩|Xi]] =𝔼Xi​[e−θ​⟨Xi,𝟙S⋆−𝟙S⟩2​MZi|Xi​(−2​θ​⟨Xi,𝟙S⋆−𝟙S⟩)] =𝔼Xi​[e−θ​⟨Xi,𝟙S⋆−𝟙S⟩2​e12​(−2​θ​⟨Xi,𝟙S⋆−𝟙S⟩)2​σ2] =𝔼Xi​[e(−θ+2​θ2​σ2)​⟨Xi,𝟙S⋆−𝟙S⟩2] =𝔼Xi​[e(−θ+2​θ2​σ2)​(∑j∈UXi​j−∑j∈VXi​j)2]. Plugging this expression into (17), we obtain: log⁡ℙ⁡(Δ≤0)≤n​infθ≥0log⁡𝔼Xi​[e(−θ+2​θ2​σ2)​(∑j∈UXi​j−∑j∈VXi​j)2]. Studying the function θ↦−θ+2​θ2​σ2 on ℝ≥0 leads to the change of variable: infθ≥0log⁡𝔼Xi​[e(−θ+2​θ2​σ2)​(∑j∈UXi​j−∑j∈VXi​j)2] (18) =infθ∈(−∞,1/(8σ2)]log𝔼Xi[e−θ​(∑j∈UXi​j−∑j∈VXi​j)2], (19) One can check that the function θ↦log⁡𝔼Xi​[e−θ​(∑j∈UXi​j−∑j∈VXi​j)2] is non-increasing over (−∞,1/(8σ2)]. Hence (19) is equal to: log𝔼Xi[e−(∑j∈UXi​j−∑j∈VXi​j)2/(8σ2)]. Therefore, the Chernoff bound yields: logℙ(Δ≤0)≤nlog𝔼Xi[e−(∑j∈UXi​j−∑j∈VXi​j)2/(8σ2)]. (20) Since U∩V=∅, we have: ∑j∈UXi​j−∑j∈VXi​j=d∑j∈U∪VXi​j. Therefore: 𝔼[e−(∑j∈UXi​j−∑j∈VXi​j)2/(8σ2)] =𝔼[e−(∑j∈U∪VXi​j)2/(8σ2)] =𝔼[e−(∑j∈U∪VBi​jNi​j)2/(8σ2)] =𝔼Bi[𝔼Ni[e−(∑j∈U∪VBi​jNi​j)2/(8σ2)|Bi]] =𝔼Bi[𝔼Ni[e−(∑j∈U∪VBi​j​Ni​j∑j∈U∪VBi​j)2×∑j∈U∪VBi​j8​σ2|Bi]]. In addition, conditionally on Bi, we have: Q≔(∑j∈U∪VBi​j​Ni​j∑j∈U∪VBi​j)2=dχ2​(1). Its MGF is: 𝔼⁡[et​Q|Bi]=MQ|Bi​(t)=11−2​t, for ​t<1/2. Hence: 𝔼Bi[𝔼Ni[e−(∑j∈U∪VBi​j​Ni​j∑j∈U∪VBi​j)2×∑j∈U∪VBi​j8​σ2|Bi]] =𝔼Bi​[MQ|Bi​(−∑j∈U∪VBi​j8​σ2)] =𝔼Bi​[2​σ4​σ2+∑j∈U∪VBi​j]. Let U[δ​s] and V[δ​s] respectively denote the sets of δ​s smallest elements of U and V. Note that this definition is legitimate since |U|=|V|=M≥δ​s. Since Bi​j≥0 for all j∈U∪V, we have: ∑j∈U∪VBi​j≥∑j∈U[δ​s]∪V[δ​s]Bi​j, and hence: 𝔼Bi​[2​σ4​σ2+∑j∈U∪VBi​j]≤𝔼Bi​[2​σ4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j]. Therefore, we get: 𝔼[e−(∑j∈UXi​j−∑j∈VXi​j)2/(8σ2)]≤𝔼Bi[2​σ4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j], and plugging this into (20) yields: log⁡ℙ⁡(Δ≤0)≤n​log⁡(𝔼Bi​[2​σ4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j]). (21) Now note that, for any i∈[n]: ∑j∈U[δ​s]∪V[δ​s]Bi​j=dBin​(2​δ​s,dp), In addition, since d=o⁡(p) and d​s/p→+∞, we have: Lemma 4.1. For any i∈[n], the following holds: as p→+∞, 12​δ​d​s/p​(∑j∈U[δ​s]∪V[δ​s]Bi​j−2​δ​d​s/p)⟶dist𝒩⁡(0,1). Proof. The proof is a simple adaptation of the proof of the Central Limit Theorem. See appendix A.1.1. Define the standardized partial sum Np≔12​δ​d​s/p​(∑j∈U[δ​s]∪V[δ​s]Bi​j−2​δ​d​s/p), which is exactly the quantity appearing in Lemma 4.1, so that Np⟶dist𝒩⁡(0,1) and in particular Np=O⁡(1). By construction, ∑j∈U[δ​s]∪V[δ​s]Bi​j=2​δ​d​s/p+2​δ​d​s/p​Np, with no remainder term, so that Vp≔2​σ​d​s/p4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j=2​σ2​δ+4​σ2d​s/p+2​δd​s/p​Np. Since d​s/p→+∞ and Np=O⁡(1), the last two terms under the root vanish in probability, hence Vp⟶ℙ2​σ2​δ=2​σ2δ. In addition, we note the following: Lemma 4.2. Vp is uniformly integrable, that is: there exists p′∈ℕ such that limT→+∞supp≥p′𝔼[|Vp|𝟙{|Vp|>T}]=0. Proof. See appendix A.1.2. Since Vp⟶ℙ2​σ2/δ and (Vp)p is uniformly integrable, the convergence holds in L1; therefore limp→+∞𝔼⁡[Vp]=2​σ2δ. Hence, we write: 𝔼Bi[2​σ4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j]=2​σ2​pδ​d​s+o((d​sp)−1/2). We conclude: log⁡ℙ⁡(Δ≤0) ≤n​log⁡(𝔼Bi​[2​σ4​σ2+∑j∈U[δ​s]∪V[δ​s]Bi​j]) =nlog(2​σ2​pδ​d​s+o((d​sp)−1/2)) =n⁡(log⁡(2​σ2​pδ​d​s)+log⁡(1+o⁡(1))) =n⁡(log⁡(2​σ2​pδ​d​s)+o⁡(1)) =n​log⁡(2​σ2​pδ​d​s)+o⁡(n), which yields the desired result: ℙ⁡(Δ≤0)≤(2​σ2​pδ​d​s)n/2​eo⁡(n). 4.2 Proof of Corollary 2 This proof relies on bringing together Theorem 1 with the following result from Wang et al. [22]. Theorem 4 (Necessary condition for sparse ensembles, Corollary 2 of [22]). Let the measurement matrix X∈ℝn×p be drawn with i.i.d. elements from the following distribution: Xi​j={𝒩⁡(0,1γ),w.p. ​γ0,w.p. ​1−γ, for all ​i∈[n],j∈[p]; (22) where γ∈(0,1]. Let λ>0 and 𝒞p,s(λ)≔{β∈ℝp||Supp(β)|=s,mini∈Supp​(β)|βi|=λ}. Assume that σ2=1. Then, in the regime where γ​s→+∞, a necessary condition for asymptotically reliable recovery over the signal class 𝒞p,s​(λ) is given by: n>log⁡(ps)−112​log⁡(1+s​λ2). While Theorem 4 is not stated on the exact same signal space 𝒞p,s​(λ) in [22] but rather on the larger: {β∈ℝp||Supp(β)|=s,mini∈Supp​(β)|βi|≥λ}, it follows directly from their result on “restricted ensembles” where the signal components under consideration are set exactly to λ (see section III.A. in [22]). 4.2.1 Necessary condition We show that (i) holds using Theorem 4, but this requires adapting our problem to the framework used by Wang et al. in [22]. In fact, note that the model used in Theorem 4 is different from the one we use in this paper, that we defined in (5). In their model, Wang et al. [22] rescale the non-zero components of X by multiplying them by 1/γ, and require that the noise variance is σ2=1. Therefore, we cannot directly use Theorem 4 in our setting. However, this difference can be fixed by a simple rescaling of our model. Note that our model defined by (5), where X follows the sparse Gaussian distribution defined in Definition 2.1 and Z∼𝒩⁡(0,σ2​In), can be equivalently written as: Y0=X0​β0⋆+Z0, Y0≔1σY,X0≔1d/pX,β0⋆≔d/pσβ⋆,andZ0≔1σZ∼𝒩(0,In). Hence, it is a particular case of the model defined in (22), with: γ≔d/pandλ≔γσ. In addition, the regime we consider of d=ω⁡(p/s) corresponds exactly to the regime considered in Theorem 4 where γ​s→+∞. Therefore, using Theorem 4, a necessary condition for an asymptotically reliable recovery of β⋆ in the considered regime is given by: n>log⁡(ps)−112​log⁡(1+s​λ2)=2​log⁡(ps)−2log⁡(1+d​s/(p​σ2))=2​log⁡(ps)log⁡(d​s/p)​(1+o⁡(1)). (23) 4.2.1.1 Sublinear regime: s=o⁡(p) Using the Corollary of Stirling: log⁡(ps)=s​log⁡(p/s)​(1+o⁡(1)), the necessary condition (23) writes: n>2​s​log⁡(p/s)log⁡(d​s/p)​(1+o​(1)). nINFSP≔2​s​log⁡(p/s)log⁡(d​s/p). Assume there exists ε>0 such that n≤(1−ε)​nINFSP. We know that, for large enough n,p,s,d we have: n≤(1−ε)​nINFSP<2​s​log⁡(p/s)log⁡(d​s/p)​(1+o⁡(1)), which contradicts the necessary condition. Therefore, it is information-theoretically impossible to ensure a reliable recovery of the support of β⋆. 4.2.1.2 Linear regime: s=α​p,α∈(0,1). Using the Corollary of Stirling: log⁡(ps)=p​h​(α)​(1+o⁡(1)), the necessary condition (23) writes: n>2​h​(α)​plog⁡d​(1+o​(1)). nINFSP≔2​h​(α)​plog⁡d. Similarly to above, we conclude that if there exists ε>0 such that n≤(1−ε)​nINFSP then it is information-theoretically impossible to ensure a reliable recovery of the support of β⋆. 4.2.2 Sufficient condition We show that (ii) holds using Theorem 1. 4.2.2.1 Sublinear regime: s=o⁡(p). Let δ>0 and: nSP⋆≔2​s​log⁡(p/s)log⁡(d​s/p)+log⁡(δ/(2​σ2)). Note that: nINFSP=2​s​log⁡(p/s)log⁡(d​s/p)=nSP⋆​(1+o⁡(1)). Assume there exists ε such that n≥(1+ε)​nINFSP. Then: n≥(1+ε)​(1+o⁡(1))​nSP⋆=(1+ε+o⁡(1))​nSP⋆≥(1+ε/2)​nSP⋆, for n,p,s,d large enough. Using Theorem 1, we have: ℙX,Z​(12​s​|Supp​(β^)​△​Supp​(β⋆)|<δ)≥1−exp⁡(−ε​s​log⁡(p/s)+o⁡(s​log⁡(p/s))). Therefore, we obtain: ℙX,Z​(12​s​|Supp​(β^)​△​Supp​(β⋆)|<δ)⟶1, as n,p,s,d→+∞. Since this holds for all δ>0, we conclude: |Supp​(β^)​△​Supp​(β⋆)|2​s⟶0, in probability, as n,p,s,d→+∞. 4.2.2.2 Linear regime: s=α​p,α∈(0,1). Let δ>0 and: nSP⋆≔2​h​(α)​plog⁡d+log⁡(δ​α/(2​σ2)). Note that: nINFSP=2​h​(α)​plog⁡d=nSP⋆​(1+o⁡(1)). Assume there exists ε such that n≥(1+ε)​nINFSP. Then: n≥(1+ε)​(1+o⁡(1))​nSP⋆=(1+ε+o⁡(1))​nSP⋆≥(1+ε/2)​nSP⋆, for n,p,s,d large enough. Using Theorem 1, we have: ℙX,Z​(12​s​|Supp​(β^)​△​Supp​(β⋆)|<δ)≥1−exp⁡(−ε​h​(α)​p+o⁡(p)). Therefore, we obtain: ℙX,Z​(12​s​|Supp​(β^)​△​Supp​(β⋆)|<δ)⟶1, as n,p,s,d→+∞. Since this holds for all δ>0, we conclude: |Supp​(β^)​△​Supp​(β⋆)|2​s⟶0, in probability, as n,p,s,d→+∞. ∎ 4.3 Proof of Example 2.2 We have d=min⁡(po⁡(1),φ−1​(o⁡(φ⁡(p)))), hence: {log⁡d/log⁡p=o⁡(1)φ⁡(d)/φ⁡(p)=o⁡(1). In addition: n1=nINF=Θ⁡(p/log⁡p),n2=nINFSP=Θ⁡(p/log⁡d). Therefore, we have: n2n1=Θ⁡(p/log⁡d)Θ⁡(p/log⁡p)=Θ⁡(log⁡plog⁡d)=ω⁡(1), On one hand, the number of samples required for reliable recovery is better in the dense case: n1=Θ⁡(p/log⁡p)=o⁡(p/log⁡d)=o⁡(n2). (24) On the other hand, the computational cost of recovering the support is better in the sparse case. In fact, matrix-vector multiplications are made easier by sparsity: in the dense case, multiplying X1 with a vector in ℝp costs: n1​p=Θ⁡(p2/log⁡p) real number multiplications, while multiplying X2 with a vector in ℝp costs n2​d=Θ⁡(p​d/log⁡d)=p​Θ​(φ⁡(d))=p​o​(φ⁡(p))=o⁡(p2/log⁡p)=o⁡(n1​p), (25) real number multiplications. This highlights the trade-off between sampling complexity and computational cost. ∎ 5 Sparse Recovery via Active Sparsification: Proof of Theorem 3 We assume, to avoid notational distractions, that α​p and ψ​p are integers; since standard rounding only affects lower-order terms. Let S⋆≔Supp​(β⋆) and let 𝒮≔{S⊂[p]:|S|=s}. For S∈𝒮, define L⁡(S)≔‖Y~−X~​𝟙S‖22. For a competing support S, write A=A⁡(S)≔S⋆∖S,B=B⁡(S)≔S∖S⋆,C=C⁡(S)≔S⋆∩S, and let M=M⁡(S)≔|A|=|B|=12​|S​△​S⋆|. We put η≔M/s∈[0,1]. For a fixed support S, set ΔS≔L⁡(S)−L⁡(S⋆). Before stating and proving the main large-deviation estimate, we outline the strategy of the proof. The argument follows the same general outline as Theorem 1: a Chernoff bound on the row-wise loss difference ΔS, followed by a union bound over supports S with |S​△​S⋆|≥2​δ​s. The technical work, however, is substantially more involved, because Y~ is not a noisy projection of the true signal through X~ but a rescaling of the original observations Y. As a result, ΔS does not decompose as cleanly as in the intrinsically-sparse setting, and its row moment generating function depends on the realization of the sparsification mask B1. The strategy is to compute the row MGF conditionally on B1. After integrating out the noise Z1, the conditional MGF takes the form 𝔼⁡[exp⁡(Uθ​Vθ)∣B1] for a centered Gaussian pair (Uθ,Vθ) whose variances and covariance are explicit polynomials in the mask sums xA​(B1),xB​(B1),xC​(B1) over the index sets A,B,C defined above (Lemma 5.1). This expression is finite only when a discriminant Dp​(θ,b)=(1−cp​(θ,b))2−ap​(θ,b)​bp​(θ,b) is positive. A natural choice of Chernoff parameter θ⋆ makes the limiting MGF collapse to a clean closed form via an algebraic cancellation (see the calculation in the proof of Lemma 5.3, where the η​ψ2 and 2−η−2​ψ​(1−η) terms combine into −Tη). The drawback is that Dp​(θ⋆,b) vanishes on a set of masks b of exponentially small probability, so directly evaluating the bound at θ⋆ would require a uniform-integrability hypothesis to justify passing to the limit. We sidestep this by evaluating the Chernoff bound at the shrunken parameter θp,λ≔λ​θ⋆ for some fixed λ∈(0,1). The factor λ<1 keeps Dp​(θp,λ,b) bounded below by a positive constant uniformly over all masks b (Lemma 5.2), hence yielding the limit by bounded convergence. The cost of this shrinkage is a degraded MGF limit: instead of (1+C)−1/2, we obtain (1+(2λ−λ2)C)−1/2 (where C>0 is a constant depending on the problem parameters, whose explicit expression we omit here for readability). Since 2​λ−λ2→1 as λ→1−, the slack ε in the sample-size assumption absorbs this loss. We now state the main large-deviation estimate, uniform over all supports whose relative error is at least δ. Proposition 5.1. Fix α,δ∈(0,1) and λ∈(0,1). There exists ψ0=ψ0​(α,δ,λ)>0 such that, for every fixed ψ∈(0,ψ0), uniformly over all S∈𝒮 with η≔M⁡(S)/s≥δ, ℙ(ΔS≤0)≤(1+(2λ−λ2)ηψC⋆(η))−n/2eo⁡(n), (26) C⋆​(η)≔ψ(1−ψ)​(2−η⁡(1−ψ)). (27) The o⁡(n) term is uniform in S and in η∈[δ,1]. Before proving Proposition 5.1, we show how it implies Theorem 3. Fix ε>0. We construct λ and ψ0 below; λ will depend only on ε and ψ0 only on (α,δ,λ), so the resulting ψ0 depends only on (α,δ,ε), as the statement requires. Step 1: choose λ. Pick λ∈(0,1) sufficiently close to one so that (1+ε)​(2​λ−λ2)>1. (28) Such λ clearly exists. Step 2: choose ψ0. The function g⁡(x)≔(1+ε)​log⁡(1+(2​λ−λ2)​x)−log⁡(1+x) satisfies g⁡(0)=0 and for any x≥0 we have by (28): g′​(x)=(1+ε)​(2​λ−λ2)1+(2​λ−λ2)​x−11+x>0, therefore g⁡(x)>0 for all x≥0. Hence, for every ψ∈(0,1) we have: (1+ε)​log⁡(1+(2​λ−λ2)​δ​ψ​C⋆​(δ))>log⁡(1+δ​ψ​C⋆​(δ)). (29) Let ψ0 be the threshold supplied by Proposition 5.1 for the chosen λ. Fix any ψ∈(0,ψ0) and assume n≥(1+ε)​nSP⋆. Step 3: union bound. By Proposition 5.1, for every support S with M⁡(S)≥δ​s, ℙ(ΔS≤0)≤(1+(2λ−λ2)ηψC⋆(η))−n/2eo⁡(n). The function η⟼η​C⋆​(η)=η​ψ(1−ψ)​(2−η⁡(1−ψ)) is increasing on [0,1]. Hence, for η≥δ: ℙ(ΔS≤0)≤(1+(2λ−λ2)δψC⋆(δ))−n/2eo⁡(n). Using the union bound over all supports of cardinality s, ℙ⁡(|Supp​(β^)​△​S⋆|≥2​δ​s) ≤∑S∈𝒮:M⁡(S)≥δ​sℙ(ΔS≤0) ≤(ps)(1+(2λ−λ2)δψC⋆(δ))−n/2eo⁡(n). Since s=α​p, Stirling’s formula gives log⁡(ps)=h⁡(α)​p+o⁡(p). Moreover, by the definition of nSP⋆, h⁡(α)​p=nSP⋆2​log⁡(1+δ​ψ​C⋆​(δ)). Note that o⁡(p)=o⁡(n) since n=Θ⁡(p) for fixed ψ. Therefore log⁡ℙ⁡(|Supp​(β^)​△​S⋆|≥2​δ​s) ≤h⁡(α)​p−n2​log⁡(1+(2​λ−λ2)​δ​ψ​C⋆​(δ))+o⁡(n) ≤nSP⋆2[log(1+δψC⋆(δ)) −(1+ε)log(1+(2λ−λ2)δψC⋆(δ))]+o(n). By (29), the bracketed term is a strictly negative constant. Since nSP⋆=Θ⁡(p) for fixed ψ, the right-hand side tends to −∞. This proves ℙ⁡(|Supp​(β^)​△​S⋆|<2​δ​s)⟶1. It remains to prove Proposition 5.1. 5.1 Conditional Chernoff transform Fix S∈𝒮 and write A,B,C,M,η as above. We have: ΔS =L⁡(S)−L⁡(S⋆) =‖dp​X​𝟙S⋆−X~​𝟙S+dp​Z‖22−‖(dp​X−X~)​𝟙S⋆+dp​Z‖22 =‖X~​𝟙S‖22−‖X~​𝟙S⋆‖22+2​dp​⟨X​𝟙S⋆+Z,X~​(𝟙S⋆−𝟙S)⟩ =∑i=1n⟨X~i,𝟙S⟩2−∑i=1n⟨X~i,𝟙S⋆⟩2+2​dp​∑i=1n(⟨Xi,𝟙S⋆⟩+Zi)​(⟨X~i,𝟙S⋆⟩−⟨X~i,𝟙S⟩) =∑i=1n(⟨X~i,𝟙S⟩2−⟨X~i,𝟙S⋆⟩2+2​ψ​(⟨Xi,𝟙S⋆⟩+Zi)​(⟨X~i,𝟙S⋆⟩−⟨X~i,𝟙S⟩)). For each row i, let Δi≔⟨X~i,𝟙S⟩2−⟨X~i,𝟙S⋆⟩2+2​ψ​(⟨Xi,𝟙S⋆⟩+Zi)​(⟨X~i,𝟙S⋆⟩−⟨X~i,𝟙S⟩). Then ΔS=∑i=1nΔi, and the Δi’s are i.i.d. For θ>0, Chernoff’s bound gives ℙ⁡(ΔS≤0)≤(𝔼⁡[e−θ​Δ1])n, (30) for all θ>0. We compute the row moment generating function. Let B1=(B1​j)j∈[p] be the first row of the sparsification mask. Conditionally on B1, integrating first over Z1∼𝒩⁡(0,σ2) yields 𝔼⁡[e−θ​Δ1∣B1]=𝔼⁡[eUθ​Vθ∣B1], (31) where we define the centered jointly Gaussian variables Uθ ≔θ⁡(∑j∈AB1​j​X1​j−∑j∈BB1​j​X1​j), Vθ ≔∑j∈A((1+γ⁡(θ))​B1​j−2​ψ)​X1​j+∑j∈B(1−γ⁡(θ))​B1​j​X1​j +2∑j∈C(B1​j−ψ)X1​j, γ⁡(θ)≔2​ψ2​σ2​θ. (32) The identity (31), with the stated forms of Uθ and Vθ, follows from a direct expansion of Δ1 and a Gaussian integration over Z1; the computation is carried out in Appendix A.2.1. We now introduce the following lemma to characterize the entity in (31). Lemma 5.1. Let (U,V) be a centered bivariate Gaussian vector. Put a≔Var⁡(U),b≔Var⁡(V),c≔Cov⁡(U,V). D≔(1−c)2−a​b>0, 𝔼[eU​V]=D−1/2. If D≤0, then the expectation is infinite. The proof Lemma 5.1 follows from a simple change of variable: see appendix A.2.3. For a deterministic mask realization b=(bj)j∈[p]∈{0,1}p, define xA​(b) ≔∑j∈Abj, xB​(b) ≔∑j∈Bbj, xC​(b) ≔∑j∈Cbj. Conditionally on B1=b, we know that since the X1​j are independent 𝒩⁡(0,1), (Uθ,Vθ) is centered and jointly Gaussian. A direct computation (Appendix A.2.2) yields its variances and covariance: ap​(θ,b) ≔Var⁡(Uθ∣B1=b)=θ2​(xA​(b)+xB​(b)), (33) bp​(θ,b) ≔Var⁡(Vθ∣B1=b) =4​ψ2​s+((1+γ⁡(θ))2−4​ψ​(1+γ⁡(θ)))​xA​(b)+(1−γ⁡(θ))2​xB​(b) +4​(1−2​ψ)​xC​(b), (34) cp​(θ,b) ≔Cov⁡(Uθ,Vθ∣B1=b) =θ⁡[(1+γ⁡(θ)−2​ψ)​xA​(b)−(1−γ⁡(θ))​xB​(b)]. (35) Put Dp​(θ,b)≔(1−cp​(θ,b))2−ap​(θ,b)​bp​(θ,b). (36) Whenever Dp​(θ,b)>0, Lemma 5.1 gives 𝔼[e−θ​Δ1∣B1=b]=Dp(θ,b)−1/2. (37) 5.2 A regularized Chernoff parameter For λ∈(0,1), define θp,λ​(η)≔λ​C⋆​(η)2​α​ψ​p=λ2​α​(1−ψ)​(2−η⁡(1−ψ))⋅1p. (38) The shrinkage factor λ<1 keeps the Gaussian product MGF uniformly inside its domain of finiteness. Lemma 5.2. Fix α,δ∈(0,1) and λ∈(0,1). There exist ψ0>0, p0∈ℕ, and κ>0 such that, for every ψ∈(0,ψ0), every p≥p0, every η∈[δ,1], and every mask b∈{0,1}p, Dp​(θp,λ​(η),b)≥κ. Consequently, 𝔼[e−θp,λ​(η)​Δ1∣B1=b]≤κ−1/2 for all such b. Write u≔xA​(b)p,v≔xB​(b)p,w≔xC​(b)p. Recall that |A|=|B|=η​s and |C|=(1−η)​s. Then 0≤u,v≤η​α and 0≤w≤(1−η)​α. Let kλ,η,ψ≔λ2​α​(1−ψ)​(2−η⁡(1−ψ)),so thatθp,λ​(η)=kλ,η,ψ/p. By (32) and (38), we have γ⁡(θp,λ​(η))=O⁡(p−1). Hence, uniformly over η∈[δ,1], ψ in [0,1), and all masks b, the expression Dp​(θp,λ​(η),b) differs by o⁡(1) from Dψ​(u,v,w,η) ≔(1−kλ,η,ψ​[(1−2​ψ)​u−v])2 −kλ,η,ψ2​(u+v)​[4​ψ2​α+(1−4​ψ)​u+v+4​(1−2​ψ)​w]. We first lower-bound the limiting expression at ψ=0. We have kλ,η,0=λ2​α​(2−η). For ψ=0, D0​(u,v,w,η) =(1−kλ,η,0​(u−v))2−kλ,η,02​(u+v)​(u+v+4​w) =1−2​kλ,η,0​(u−v)−4​kλ,η,02​[u​v+w⁡(u+v)]. The right-hand side is decreasing in w, so its minimum over the allowed interval for w is attained at w=(1−η)​α. With this value of w, the derivative in v equals 2​kλ,η,0−4​kλ,η,02​[u+(1−η)​α]=2​kλ,η,0​[1−2​kλ,η,0​[u+(1−η)​α]]≥0, because u+(1−η)​α≤α (recall that u≤η​α) and 2​kλ,η,0​α=λ/(2−η)<1. Hence the minimum is attained at v=0. The resulting expression, D0​(u,0,(1−η)​α,η)=1−2​kλ,η,0​u−4​kλ,η,02​(1−η)​α​u, is decreasing in u, and hence the minimum is attained at u=η​α. Therefore D0​(u,v,w,η) ≥1−η​α​(2​kλ,η,0+4​kλ,η,02​(1−η)​α) =1−2​λ​η​α2​α​(2−η)−4​η​α​(1−η)​α​λ24​α2​(2−η)2 =1−λ​η2−η−λ2​η⁡(1−η)(2−η)2 ≥1−λ, where the last inequality holds because λ≤1 and η2−η+η⁡(1−η)(2−η)2≤1,∀η∈[0,1]. By continuity of Dψ in ψ∈[0,1), uniformly over the same compact domain, there exists ψ0>0 such that Dψ​(u,v,w,η)≥1−λ2 for all ψ∈(0,ψ0). The uniform o⁡(1) approximation between Dp and Dψ then gives the claim, after setting κ≔(1−λ)/4, and p0 large enough (recall that Dp​(θp,λ​(η),b) and Dψ​(u,v,w,η) differ by o⁡(1)). ∎ Lemma 5.3. Fix α,δ∈(0,1) and λ∈(0,1), and take ψ>0 small enough for Lemma 5.2 to hold. Then we have, uniformly over η∈[δ,1], 𝔼[e−θp,λ​(η)​Δ1]=(1+(2λ−λ2)ηψC⋆(η))−1/2+o(1). (39) Up≔xA​(B1)p,Vp≔xB​(B1)p,Wp≔xC​(B1)p. Since |A|=|B|=η​α​p and |C|=(1−η)​α​p, the three variables are sums of i.i.d. Bernoulli(ψ) terms divided by p. For every ρ>0, Hoeffding’s inequality applied to SA:=∑j∈AB1​j gives ℙ⁡(|Up−η​α​ψ|>ρ) =ℙ⁡(|SA−η​α​p​ψ|>ρ​p) ≤2​exp⁡(−2​ρ2​p2|A|) =2​exp⁡(−2​ρ2​pη​α) ≤2​exp⁡(−2​ρ2​pα), where the last inequality uses η≤1. The same bound holds for Vp. For Wp, the analogous computation with |C|=(1−η)​α​p gives, for η∈[δ,1), ℙ⁡(|Wp−(1−η)​α​ψ|>ρ)≤2​exp⁡(−2​p​ρ2(1−η)​α)≤2​exp⁡(−2​p​ρ2(1−δ)​α); for η=1, Wp≡0=(1−η)​α​ψ and the probability vanishes. Each right-hand side is independent of η and tends to zero as p→∞, so supη∈[δ,1]ℙ⁡(|Up−η​α​ψ|>ρ)→0, and analogously for Vp,Wp. Hence (Up,Vp,Wp)⟶(η​α​ψ,η​α​ψ,(1−η)​α​ψ) in probability, uniformly in η∈[δ,1]. Fp(u,v,w;η)≔Dp(θp,λ(η),b)−1/2, where u=xA​(b)/p, v=xB​(b)/p, and w=xC​(b)/p. By Lemma 5.2, 0≤Fp≤κ−1/2 for all masks and all η∈[δ,1]. Define the compact set K≔{(u,v,w,η):0≤u,v≤ηα, 0≤w≤(1−η)α,η∈[δ,1]}. On K, the polynomial formula (36) together with θp,λ​(η)=O⁡(p−1) and γ⁡(θp,λ)=O⁡(p−1) (uniformly in η) gives Dp→D∞ uniformly, where D∞​(u,v,w,η) is the polynomial obtained by setting γ=0 in (36). Combined with the uniform lower bound Dp≥κ>0 and the Lipschitz continuity of x↦x−1/2 on [κ,∞), this yields sup(u,v,w,η)∈K|Fp​(u,v,w,η)−F∞​(u,v,w,η)|⟶0, where F∞≔D∞−1/2. Combining this uniform convergence with the concentration (Up,Vp,Wp)→(η​α​ψ,η​α​ψ,(1−η)​α​ψ) in probability (uniformly in η) and the uniform continuity of F∞ on K, we obtain Fp​(Up,Vp,Wp,η)⟶F∞​(η​α​ψ,η​α​ψ,(1−η)​α​ψ,η) in probability, uniformly in η∈[δ,1]. Since Fp≤κ−1/2, bounded convergence yields supη∈[δ,1]|𝔼B[Dp(θp,λ(η),B1)−1/2]−F∞(ηαψ,ηαψ,(1−η)αψ;η)|⟶0. Substituting u=v=η​α​ψ,w=(1−η)​α​ψ,θp,λ​(η)=λ​C⋆​(η)2​α​ψ​p, into (33), (34) and (35); and using γ⁡(θp,λ)=o⁡(1), we obtain cp ⟶−λ​η​ψ​C⋆​(η), ap​bp ⟶λ2​η​ψ​C⋆​(η)​(1+η​ψ​C⋆​(η)), which yields: (1−cp)2−ap​bp ⟶1+(2​λ−λ2)​η​ψ​C⋆​(η). We spell out the cancellation in detail. Let Tη≔(1−ψ)​(2−η⁡(1−ψ)),so thatC⋆​(η)=ψ/Tη. At the mean mask profile, cp ⟶−2​kλ,η,ψ​η​α​ψ2=−λ​η​ψ​C⋆​(η), ap​bp ⟶4​kλ,η,ψ2​η​α2​ψ2​[2−η−2​ψ​(1−η)]. Thus limp→∞Dp =(1+λ​η​ψ​C⋆​(η))2−4​kλ,η,ψ2​η​α2​ψ2​[2−η−2​ψ​(1−η)] =1+2​λ​η​ψ​C⋆​(η)+λ2​η2​ψ2​C⋆​(η)2 −λ2​η​C⋆​(η)2​[2−η−2​ψ​(1−η)] =1+2​λ​η​ψ​C⋆​(η)+λ2​η​C⋆​(η)2​[η​ψ2−2+η+2​ψ​(1−η)]. The term in brackets equals −Tη, and since C⋆​(η)=ψ/Tη, this becomes 1+2​λ​η​ψ​C⋆​(η)−λ2​η​ψ​C⋆​(η)=1+(2​λ−λ2)​η​ψ​C⋆​(η). Combining this with (37) completes the proof of (39). ∎ Fix S∈𝒮 with M⁡(S)≥δ​s, and let η=M⁡(S)/s. Apply Chernoff’s bound (30) with θ=θp,λ​(η). Lemma 5.3 gives, uniformly in S, 𝔼[e−θp,λ​(η)​Δ1]=(1+(2λ−λ2)ηψC⋆(η))−1/2+o(1). The limiting quantity is a constant in (0,1) for any η∈[δ,1], raising to the n-th power yields ℙ(ΔS≤0)≤(1+(2λ−λ2)ηψC⋆(η))−n/2eo⁡(n), hence completing the proof of (26). ∎ 6 Conclusion and Future Work In the first part of this paper, we have studied the problem of recovery of a binary signal β⋆∈{0,1}p based on a sparse measurement matrix and noisy observations. Our main result is that, if the measurements have density rate d/p then, assuming that the measurements and the signal are together not too sparse – in particular if d​s=ω⁡(p), i.e. high-SNR regime – it is possible to recover the true support asymptotically when the sample size is larger than the threshold given by Theorem 1. Combining our work with the necessary conditions of Wang et al. [22], we reveal an information-theoretic phase transition. The expression of the phase-transition threshold makes the price of sparsity explicit, revealing a precise trade-off between sampling complexity and measurement sparsity. In the following, we present a quick summary of all – to the best of our knowledge – results on sparse recovery in the sparse measurement setting, along with some future work directions. Information-theoretic threshold, sufficient conditions. In Theorem 1, we establish a sufficient condition for reliable recovery. However, this result is conditional on the high-SNR (d​s/p→+∞) assumption. This raises the question of sufficient conditions when the measurements and signal are even more sparse. Informational-theoretic threshold, necessary conditions. – Wang et al. [22] have studied this problem. Their work reveals three regimes of behavior depending on the scaling of the expected number of non-zeros of β⋆ aligning with non-zeros of a row of X: d​s/p=ω⁡(1), d​s/p→τ for some τ>0, and d​s/p=o⁡(1). For their model, where the variance of the non-zero components of X scales in a way that makes the second moment of the projected signal X​β⋆ remain the same as in the dense case: the necessary condition threshold is on the order of magnitude of the one in the dense case in the regime where d​s/p=ω⁡(1), while it increases dramatically in the regime where d​s/p=o⁡(1). – In the dense setting, Reeves et al. [19] have shown that even the recovery of a fixed fraction of the support is information theoretically impossible below the phase transition threshold: this is what they call the all-or-nothing property. It would be interesting to extend this property to the sparse setting. Algorithmic threshold, sufficient conditions. Omidiran and Wainwright [18] have shown that under a low-sparsity assumption on the measurements, the sufficient condition of the dense setting, i.e. n≥(1+ε)​nALG, is sufficient for the sparse setting as well. It would be interesting to explore the question of polynomial-time recovery in a stronger sparsity regime. Algorithmic threshold, necessary conditions. Although we cannot really hope to provide necessary conditions for polynomial-time recovery – unless conditionally on P≠NP – it would be interesting to provide a threshold under which the problem is believed to be algorithmically hard, as done by Gamarnik and Zadik [9] in the dense setting. In the second part of this paper, we have studied the problem of recovering the signal based on sparsified – but originally dense – measurements and accordingly-rescaled observations. Our main result is that, in the proportional sparsity and proportional sparsification regime where s=α​p and d=ψ​p, with ψ>0 fixed and sufficiently small, it is possible to recover the true support asymptotically when the sample size is larger than a threshold given by Theorem 3. This provides a sufficient recovery guarantee for all sufficiently small fixed ψ, provided a large enough sample size, and gives an upper bound on the price of sparsification in this regime. Nevertheless, we believe that the sparsification problem is infeasible for strong enough regimes of sparsification. In particular, we conjecture that the recovery is information-theoretically impossible no matter the sample size in the sub-proportional sparsification regime where d=o⁡(p). We leave the exploration of this regime for future work. References [1] S. Aeron, V. Saligrama, and M. Zhao (2010) Information theoretic bounds for compressed sensing. IEEE Transactions on Information Theory 56 (10), pp. 5111–5130. External Links: Document Cited by: §1.1. [2] E. J. Candès, J. Romberg, and T. Tao (2006) Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory 52 (2), pp. 489–509. Cited by: §1. [3] S. S. Chen, D. L. Donoho, and M. A. Saunders (2001) Atomic decomposition by basis pursuit. SIAM review 43 (1), pp. 129–159. Cited by: §1. [4] G. Cormode and M. Hadjieleftheriou (2009) Finding the frequent items in streams of data. Communications of the ACM 52 (10), pp. 97–105. Cited by: §1. [5] D. L. Donoho (2006) Compressed sensing. IEEE Transactions on information theory 52 (4), pp. 1289–1306. Cited by: §1. [6] D. Du and F. K. Hwang (1999) Combinatorial group testing and its applications. Vol. 12, World Scientific. Cited by: §1. [7] H. El Cheairi, D. Gamarnik, and R. Mazumder (2025) Theoretical compression bounds for wide multilayer perceptrons. arXiv preprint arXiv:2512.06288. Cited by: §1.2. [8] S. Foucart and H. Rauhut (2013) A mathematical introduction to compressive sensing. Applied and Numerical Harmonic Analysis, Birkhäuser, New York. External Links: Document Cited by: §1.2, §1. [9] D. Gamarnik and I. Zadik (2022) Sparse high-dimensional linear regression. estimating squared error and a phase transition. The Annals of Statistics 50 (2), pp. 880–903. Cited by: 2nd item, §1.1, 1st item, Table 1, Table 1, 4th item. [10] A. Gilbert and P. Indyk (2010) Sparse recovery using sparse matrices. Proceedings of the IEEE 98 (6), pp. 937–947. Cited by: §1.1. [11] B. Hassibi and D. Stork (1992) Second order derivatives for network pruning: Optimal Brain Surgeon. In Advances in Neural Information Processing Systems, Vol. 5. Cited by: §1.2. [12] T. Hastie, R. Tibshirani, and J. Friedman (2009) The elements of statistical learning: data mining, inference, and prediction. 2 edition, Springer Series in Statistics, Springer, New York. External Links: Document Cited by: §1. [13] P. Indyk (2007) Sketching, streaming and sublinear-space algorithms. Lecture notes. 33, pp. 617. Cited by: §1. [14] Y. LeCun, J. Denker, and S. Solla (1989) Optimal brain damage. In Advances in Neural Information Processing Systems, Vol. 2. Cited by: §1.2. [15] P. Loh and M. J. Wainwright (2011) High-dimensional regression with noisy and missing data: provable guarantees with non-convexity. Advances in neural information processing systems 24. Cited by: §1.2. [16] A. Miller (2002) Subset selection in regression. chapman and hall/CRC. Cited by: §1. [17] S. Muthukrishnan et al. (2005) Data streams: algorithms and applications. Foundations and Trends® in Theoretical Computer Science 1 (2), pp. 117–236. Cited by: §1. [18] D. Omidiran and M. J. Wainwright (2008) High-dimensional subset recovery in noise: sparsified measurements without loss of statistical efficiency. arXiv preprint arXiv:0805.3005. Cited by: §1.1, 5th item, 5th item, Table 1, Table 1, 3rd item. [19] G. Reeves, J. Xu, and I. Zadik (2019) The all-or-nothing phenomenon in sparse linear regression. In Conference on Learning Theory, pp. 2652–2663. Cited by: 1st item, §1.1, 1st item, §2.1, Table 1, Table 1, Remark 2.1, 2nd item. [20] R. Tibshirani (1996) Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology 58 (1), pp. 267–288. Cited by: 3rd item. [21] M. J. Wainwright (2009) Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ1-constrained quadratic programming (lasso). IEEE transactions on information theory 55 (5), pp. 2183–2202. Cited by: 3rd item, Table 1. [22] W. Wang, M. J. Wainwright, and K. Ramchandran (2010) Information-theoretic limits on sparse signal recovery: dense versus sparse measurement matrices. IEEE Transactions on Information Theory 56 (6), pp. 2967–2979. Cited by: §1.1, §1.1, §1.1, §2.1, §2.2, §2.2, Table 1, Table 1, Remark 2.1, §4.2.1, §4.2, §4.2, §4.2, 1st item, §6, Theorem 4. A Omitted Proofs A.1 Omitted Proofs from Theorem 1 A.1.1 Proof of Lemma 4.1 Np≔12​δ​d​s/p​(∑j∈U[δ​s]∪V[δ​s]Bi​j−2​δ​d​s/p). Its characteristic function writes: ΦNp​(t) =𝔼⁡[ei​t​Np] =e−i​t​2​δ​d​s/p​(𝔼⁡[exp⁡(i​t​Bi​j/2​δ​d​s/p)])2​δ​s =e−i​t​2​δ​d​s/p​(1−d/p+d/p​exp⁡(i​t/2​δ​d​s/p))2​δ​s =e−i​t​2​δ​d​s/p​(1+d/p⁡(exp⁡(i​t/2​δ​d​s/p)−1))2​δ​s =e−i​t​2​δ​d​s/p​(1+d/p⁡(i​t2​δ​d​s/p−t24​δ​d​s/p+𝒪⁡(−i​t3(2​δ​d​s/p)3/2)))2​δ​s =e−i​t​2​δ​d​s/p​(1+d/p⁡(i​t2​δ​d​s/p−t24​δ​d​s/p+𝒪⁡(1(2​δ​d​s/p)3/2)))2​δ​s =exp⁡(−i​t​2​δ​d​s/p+2​δ​s​log⁡(1+d/p⁡(i​t2​δ​d​s/p−t24​δ​d​s/p+𝒪⁡(1(2​δ​d​s/p)3/2)))) =e−i​t​2​δ​d​s/p​exp⁡(2​δ​s​(d/p⁡(i​t2​δ​d​s/p−t24​δ​d​s/p+𝒪⁡(1(2​δ​d​s/p)3/2))+𝒪⁡(ds​p))) =exp⁡(−i​t​2​δ​d​s/p+i​t​2​δ​d​s/p−t2/2+𝒪⁡(12​δ​d​s/p)+𝒪⁡(2​δ​dp)) =exp(−t2/2+o(1))⟶p→+∞exp(−t2/2)=Φ𝒩⁡(0,1)(t), for all t∈ℝ. The result follows. ∎ A.1.2 Proof of Lemma 4.2 Write Σp≔∑j∈U[δ​s]∪V[δ​s]Bi​j∼Bin​(2​δ​s,d/p), with mean μp≔𝔼⁡[Σp]=2​δ​d​s/p. We recall: Np=Σp−μpμp,Vp=2​σ2​δ+4​σ2d​s/p+2​δd​s/p​Np, and note the deterministic bound 0≤Vp≤d​s/p, which holds because Σp≥0. Fix T>2. Splitting on ℰp≔{Np≥−(ds/p)1/4}, we have: 𝔼[Vp 1{Vp>T}]=Ξ1+Ξ2,Ξ1≔𝔼[Vp 1{Vp>T} 1ℰp],Ξ2≔𝔼[Vp 1{Vp>T} 1ℰpc]. Bounding Ξ1. On ℰp the denominator defining Vp satisfies 2δ+4​σ2d​s/p+2​δd​s/pNp≥ 2δ+4​σ2d​s/p−2​δ(d​sp)−1/4. The right-hand side is deterministic and converges to 2​δ, so there is p1∈ℕ with right-hand side ≥δ for all p≥p1. Hence Vp≤2​σ/δ on ℰp for p≥p1, so 𝟙{Vp>T}𝟙ℰp≤𝟙{2σ/δ>T} and Ξ1≤2​σδ 1{2σ/δ>T},p≥p1. Bounding Ξ2. By Vp≤d​s/p we have 𝟙{Vp>T}≤𝟙{ds/p>T2}, and therefore: Ξ2≤d​s/p 1{ds/p>T2}ℙ(ℰpc). The complementary event is a Binomial lower-tail deviation: ℰpc={Σp<(1−εp)μp} with εp≔(ds/p)−1/4/2​δ∈(0,1) for p large. The multiplicative Chernoff bound ℙ(Σp≤(1−ε)μp)≤e−ε2μp/2 gives ℙ⁡(ℰpc)≤exp⁡(−εp2​μp2)=exp⁡(−d​s/p2),εp2​μp=12​δ​d​s/p⋅2​δ​d​sp=d​s/p. Hence, for p≥p2 (large enough that εp∈(0,1)), we have: Ξ2≤d​s/pe−d​s/p/2 1{ds/p>T2}. On {ds/p>T2} we have d​s/p>T>2, and x↦xe−x/2 is decreasing for x>2, so Ξ2≤Te−T/2. We conclude that, for all p≥p′≔max⁡(p1,p2), we have: 𝔼[Vp 1{Vp>T}]≤2​σδ 1{2σ/δ>T}+Te−T/2. The right-hand side is independent of p and tends to 0 as T→+∞ (the first term vanishes once T>2​σ/δ). Therefore limT→+∞supp≥p′𝔼[Vp 1{Vp>T}]=0. A.2 Omitted Proofs from Theorem 3 A.2.1 Derivation of the conditional row moment generating function We work with the first row and abbreviate Xj≡X1​j, Bj≡B1​j, Z≡Z1. Since 𝟙S⋆=𝟙A+𝟙C, 𝟙S=𝟙B+𝟙C, and X~1​j=Bj​Xj, set W≔∑j∈ABj​Xj−∑j∈BBj​Xj=⟨X~1,𝟙S⋆−𝟙S⟩, R≔∑j∈ABj​Xj+∑j∈BBj​Xj+2​∑j∈CBj​Xj=⟨X~1,𝟙S⋆⟩+⟨X~1,𝟙S⟩, and D≔∑j∈S⋆Xj=⟨X1,𝟙S⋆⟩. Expanding Δ1. Factoring the difference of squares in the definition of Δ1 and using ⟨X~1,𝟙S⟩−⟨X~1,𝟙S⋆⟩=−W, we get: ⟨X~1,𝟙S⟩2−⟨X~1,𝟙S⋆⟩2=(⟨X~1,𝟙S⟩−⟨X~1,𝟙S⋆⟩)​(⟨X~1,𝟙S⟩+⟨X~1,𝟙S⋆⟩)=−W​R, while the cross term equals 2​ψ​(D+Z)​W. Hence Δ1=−W​R+2​ψ​(D+Z)​W=W⁡(2​ψ​D−R)+2​ψ​W​Z, and therefore: −θ​Δ1=θ​W​(R−2​ψ​D)−2​θ​ψ​W​Z. Integrating out Z. Only the final term involves Z. Conditioning on (X1,B1) and integrating Z∼𝒩⁡(0,σ2), 𝔼[e−2​θ​ψ​W​Z∣X1,B1]=e12​(2​θ​ψ​W)2​σ2=e2​θ2​ψ2​σ2​W2=eθ​γ​(θ)​W2, where the last equality holds by γ⁡(θ)=2​ψ2​σ2​θ from (32). Therefore 𝔼⁡[e−θ​Δ1∣B1] =𝔼X1​[exp⁡(θ​W​(R−2​ψ​D)+θ​γ​(θ)​W2)∣B1] =𝔼X1​[exp⁡(θ​W​(R−2​ψ​D+γ⁡(θ)​W))∣B1]. With Uθ≔θ​W and Vθ≔R−2​ψ​D+γ⁡(θ)​W, the exponent is Uθ​Vθ, which is (31). Explicit form of Uθ,Vθ. Now we have: Uθ=θ​W=θ⁡(∑j∈ABj​Xj−∑j∈BBj​Xj). Regrouping Vθ by index set, we obtain: Vθ =(∑j∈ABj​Xj+∑j∈BBj​Xj+2​∑j∈CBj​Xj)−2​ψ​(∑j∈AXj+∑j∈CXj) +γ⁡(θ)​(∑j∈ABj​Xj−∑j∈BBj​Xj) =∑j∈A((1+γ⁡(θ))​Bj−2​ψ)​Xj+∑j∈B(1−γ⁡(θ))​Bj​Xj+2​∑j∈C(Bj−ψ)​Xj, matching the definitions in Section 5. Since Uθ and Vθ are linear in the Gaussian vector X1 with coefficients determined by B1, the pair (Uθ,Vθ) is, conditionally on B1, centered and jointly Gaussian. ∎ A.2.2 Conditional variances and covariance of the Gaussian pair Fix a mask realization B1=b and abbreviate Xj≡X1​j, γ≡γ⁡(θ). Conditionally on B1=b, the Xj are independent 𝒩⁡(0,1), so Uθ and Vθ, being linear in (Xj)j∈[p], are centered and jointly Gaussian, and their conditional second moments are obtained by summing products of their Xj-coefficients over j, the sets A,B,C being disjoint. Throughout we use bj∈{0,1}, hence bj2=bj, together with |A|+|C|=|S⋆|=s. Reading off the definitions of Uθ and Vθ in Section 5, the Xj-coefficients of Uθ are θ​bj on A, −θ​bj on B, and 0 on C; those of Vθ are (1+γ)​bj−2​ψ on A, (1−γ)​bj on B, and 2​(bj−ψ) on C. Variance of Uθ. Summing the squared coefficients, we obtain: Var⁡(Uθ∣B1=b)=θ2​∑j∈Abj2+θ2​∑j∈Bbj2=θ2​(xA​(b)+xB​(b)), which is (33). Variance of Vθ. The per-coordinate squared coefficients are j∈A: ((1+γ)​bj−2​ψ)2=((1+γ)2−4​ψ​(1+γ))​bj+4​ψ2, j∈B: ((1−γ)​bj)2=(1−γ)2​bj, j∈C: (2​(bj−ψ))2=4​(1−2​ψ)​bj+4​ψ2, using bj2=bj. Summing over each set and combining the constant 4​ψ2 terms through |A|+|C|=s, we obtain: Var⁡(Vθ∣B1=b)=4​ψ2​s+((1+γ)2−4​ψ​(1+γ))​xA​(b)+(1−γ)2​xB​(b)+4​(1−2​ψ)​xC​(b), which is (34). Covariance. The Uθ-coefficient vanishes on C, so only A and B contribute: Cov⁡(Uθ,Vθ∣B1=b) =∑j∈A(θ​bj)​((1+γ)​bj−2​ψ)+∑j∈B(−θ​bj)​((1−γ)​bj) =θ​∑j∈A((1+γ)−2​ψ)​bj−θ​∑j∈B(1−γ)​bj =θ⁡[(1+γ−2​ψ)​xA​(b)−(1−γ)​xB​(b)], which is (35). ∎ A.2.3 Proof of Lemma 5.1 The covariance matrix Σ=(accb) is positive semidefinite, so detΣ=a​b−c2≥0. We split according to whether Σ is positive definite (a​b>c2) or degenerate (a​b=c2); the degenerate case is further divided into two sub-cases. Case 1: Σ≻0. For G=(U,V)⊺, since U​V=12​G⊺​J​G, where J=(0110), the standard quadratic-form Gaussian MGF formula gives 𝔼[eU​V]=det(I−ΣJ)−1/2 provided Σ−1−J≻0; otherwise the integral diverges. Since det(Σ−1−J)=det(Σ−1)​det(I−Σ​J)=((1−c)2−a​b)/det(Σ) and det(Σ)=a​b−c2>0 by positive definiteness, the condition Σ−1−J≻0 is equivalent to D=(1−c)2−a​b>0. Computing I−Σ​J=(1−c−a−b1−c), we obtain det(I−Σ​J)=(1−c)2−a​b=D, proving the claim. Case 2: Σ is degenerate with a=0 or b=0. Then c2=a​b forces c=0, so U=0 a.s. or V=0 a.s. In either case, U​V=0 a.s. and 𝔼⁡[eU​V]=1, which agrees with D=(1−c)2−a​b=1, so D−1/2=1. Case 3: Σ is degenerate with a,b>0. Then c2=a​b, so V=(c/a)​U a.s. with U∼𝒩⁡(0,a). Hence U​V=(c/a)​U2 where U2/a∼χ12, giving 𝔼[eU​V]=𝔼[ec⋅U2/a]=(1−2c)−1/2if c<1/2, and +∞ otherwise. On the other hand, D=(1−c)2−a​b=(1−c)2−c2=1−2​c, so the formula 𝔼[eU​V]=D−1/2 holds, and the D>0 condition matches. ∎