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 \left(p/s\right)/\log \left(ds/p\right)$, 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=\alpha p$, $d=\psi p$, we prove that, for every fixed target error level $\delta$ and every slack $\epsilon >0$, a sample size of order $p/{\psi }^2$ is sufficient for support recovery for arbitrarily small $\psi$.

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 ${\beta }^{\star }\in {ℝ}^p$, unknown but a priori $s$-sparse for some given $s\le p$, a random measurement matrix $X\in {ℝ}^{n\times p}$ (also referred to as design, features or data) and a noise vector $Z\sim 𝒩(0,{\sigma }^2{I}_n)$, where $n\in \mathbb{N}$ denotes the sample size and ${\sigma }^2>0$ a fixed constant. A vector of observations (also known as labels or annotations) is given by:

$Y≔X{\beta }^{\star }+Z.$

Sparse recovery refers to reconstructing ${\beta }^{\star }$ given $X$ and $Y$. Intuitively, this problem can be reduced to recovering the support $S^{\star }$ of ${\beta }^{\star }$, i.e. the set of indices of its non-zero components. In fact, once the support $S^{\star }$ is identified, the full signal can be estimated using the corresponding columns of $X$ via the closed-form maximum-likelihood estimator formula ${\beta }_{\text{MLE}}=X_{S^{\star }}^{+}Y$, where $X_{S^{\star }}^{+}$ denotes the Moore-Penrose pseudoinverse of the submatrix formed by the columns of $X$ with indices in $S^{\star }$ [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 $n_{\text{INF}}<n_{\text{ALG}}$, yielding three regimes:

• $n<n_{\text{INF}}$: impossibility of recovery. Reeves et al. [19] show that if $n\le \left(1-\epsilon \right)n_{\text{INF}}$ then the recovery of any fraction of the support of the signal is information-theoretically impossible.

• $n_{\text{INF}}<n<n_{\text{ALG}}$: super-polynomial complexity. Gamarnik and Zadik [9] show that if $n\ge \left(1+\epsilon \right)n_{\text{INF}}$ then the maximum-likelihood estimator (MLE) recovers the support of ${\beta }^{\star }$. Although solvable, the problem is widely believed to be algorithmically hard since the MLE exhibits an Overlap Gap Property (OGP) [9].

• $n>n_{\text{ALG}}$: polynomial-time recovery. Wainwright [21] shows that if $n\ge \left(1+\epsilon \right)n_{\text{ALG}}$ then the Lasso [20], which is a polynomial-time algorithm, succeeds in recovering the support of ${\beta }^{\star }$.

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 $ds/p$, the expected number of non-zero components of ${\beta }^{\star }$ that align with non-zero components of a row of $X$. The three regimes are: $ds/p\to +\infty$, $ds/p=\tau$ for some constant $\tau >0$, and $ds/p\to 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 $ds/p\to +\infty$, 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 $ds/p\to 0$. They work with entries rescaled so that $\mathrm{Var}\left(X{\beta }^{\star }\right)$ matches the dense case, while we keep $\mathrm{Var}\left(X_{ij}\right)=1$. The settings are equivalent since any scaling of $X$ can be accounted for in ${\beta }^{\star }$.

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. ${\beta }^{\star }\in {\{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. ${\beta }^{\star }\in \{\beta \in {ℝ}^p:{\Vert \beta \Vert }_0=s\text{ and }{\min }_{j\in \left[p\right]:{\beta }_j\ne 0}\left|{\beta }_j\right|\ge 1\}$. Our first main result (Theorem 1) states that in the high signal-to-noise ratio (SNR) regime where $ds/p\to +\infty$, if the number of samples $n$ is larger than a threshold given by:

$n_{\text{INF}}^{\text{SP}}=\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)},$

(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 $n_{\text{INF}}^{\text{SP}}$. In particular, if there exists a constant $\epsilon >0$ such that $n\le \left(1-\epsilon \right)n_{\text{INF}}^{\text{SP}}$ then it is information-theoretically impossible to ensure a reliable recovery of the support of the signal, and if there exists a constant $\epsilon >0$ such that $n\ge \left(1+\epsilon \right)n_{\text{INF}}^{\text{SP}}$ 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 $\Gamma =\log s/\log \left(ds/p\right)$, quantifying the sampling complexity vs. measurement sparsity trade-off. In particular, we note that in the proportional regime $s=\Theta \left(p\right)$, $d=\Theta \left(p\right)$, 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:

$n_{\text{ALG}}=2s\log \left(p-s\right),$

specifically for the Lasso to ensure a reliable polynomial time recovery of ${\beta }^{\star }$. Although the sparsity assumption under which this result holds allows for the density rate $d/p$ to go to $0$ as $p\to +\infty$, it still doesn’t allow the measurements to be very sparse. In fact, it requires that:

$d/p=\omega \left(s^{-1/3}\right)\text{and}d/p=\omega \left({\left(\frac{\log \log \left(p-s\right)}{\log \left(p-s\right)}\right)}^{1/3}\right).$

(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 $\tilde{X}$ by setting each entry of $X$ to zero independently with probability $1-d/p$, keeping it unchanged otherwise. Equivalently, ${\tilde{X}}_{ij}≔B_{ij}{X}_{ij}$ where $B_{ij},i\in \left[n\right],j\in \left[p\right]$ are i.i.d. $\text{Ber}\left(d/p\right)$ random variables independent of $X$, and $d\le p$ controls the sparsification rate. The dense observations $Y=X{\beta }^{\star }+Z$ are then rescaled accordingly to form $\tilde{Y}≔\left(d/p\right)Y$, and recovery is attempted from $(\tilde{X},\tilde{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 ${\ell }_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=\alpha p$ and $d=\psi p$, with $\alpha \in (0,1)$ fixed and $\psi >0$ fixed and sufficiently small. Specifically, our second main result (Theorem 3) states that, for every fixed error tolerance $\delta \in (0,1)$ and every slack $\epsilon >0$, there exists ${\psi }_0={\psi }_0(\alpha ,\delta ,\epsilon )>0$ such that, for every fixed $\psi \in (0,{\psi }_0)$, a sample size $n$ larger than the threshold

$\frac{2h\left(\alpha \right)p}{\log \left(1+\frac{\delta {\psi }^2}{\left(1-\psi \right)\left(2-\delta \left(1-\psi \right)\right)}\right)}$

(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 $\delta$. The proof of Theorem 3 is substantially more involved than that of Theorem 1 because the rescaled observations $\tilde{Y}$ are a rescaling of the original observations $Y$, not a noisy projection of the true signal through the sparsified design $\tilde{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\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$ absorbs. The smallness condition on $\psi$ is precisely the cost of this regularization, not a claim that larger $\psi$ is intrinsically harder. We believe this regularized Chernoff parameter device is of independent methodological interest. In the strong-sparsification regime where $\psi \to 0$, the sufficient threshold (3) effectively writes:

$n_{\text{INF}}^{\text{SP}}=\Theta \left(\frac{p}{{\psi }^2}\right).$

(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=\Omega \left(p\right)$, recovery upon active sparsification holds as long as $\psi \ge c\sqrt{p/n}$, for some constant $c>0$. Explicitly: a practitioner with $n$ observations may zero out all but an order-$\sqrt{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 $\sqrt{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 ${\theta }_{p,\lambda }=\lambda {\theta }^{\star }$ for $\lambda \in (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(\cdot )$ the binary entropy: $h\left(x\right)=-x\log x-\left(1-x\right)\log \left(1-x\right)$, $x\in (0,1)$. We call ${\ell }_0$-norm the number of non-zero coordinates of $x\in {ℝ}^d$, that is ${\Vert x\Vert }_0≔{\sum }_{i=1}^d\mathrm{𝟙}\left(x_i\ne 0\right)$. We call support of $u\in {ℝ}^p$ the set of indices of the non-zero components of $u$ and denote it $\text{Supp}\left(u\right)≔\{i\in \left[p\right]:u_i\ne 0\}$, so that $\left|\text{Supp}\left(u\right)\right|={\Vert u\Vert }_0$. We call symmetric difference between two sets $S_1$ and $S_2$ the set of elements in one but not the other and denote it $S_1△S_2≔\left(S_1\cup S_2\right)\setminus \left(S_1\cap S_2\right).$

2 Sparse Recovery using Sparse Measurements

2.1 Setting

Let $n,p,s,d\in \mathbb{N}$ such that $d,s\le p$. We define a sparse Gaussian matrix in ${ℝ}^{n\times p}$ as follows.

Definition 2.1 (Sparse Gaussian matrix).

We call $X={\left[X_{ij}\right]}_{i\in \left[n\right],j\in \left[p\right]}\in {ℝ}^{n\times p}$ a sparse Gaussian matrix with parameter $d$ if for all $i\in \left[n\right],j\in \left[p\right]$ we have:

$X_{ij}=B_{ij}{N}_{ij},$

where ${\left(B_{ij}\right)}_{i\in \left[n\right],j\in \left[p\right]}\stackrel{\text{i.i.d.}}{\sim }\text{Ber}\left(d/p\right)$ and ${\left(N_{ij}\right)}_{i\in \left[n\right],j\in \left[p\right]}\stackrel{\text{i.i.d.}}{\sim }𝒩(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\left(p\right)$.

Let $X$ be a sparse Gaussian random matrix of parameter $d$, and $Z$ be a random vector in ${ℝ}^n$ such that $Z\sim 𝒩(0,{\sigma }^2{I}_n)$, with $\sigma >0$ a fixed constant. Let ${\beta }^{\star }\in {\{0,1\}}^p$ be a deterministic vector such that ${\Vert {\beta }^{\star }\Vert }_0=s$. We define the random vector $Y$ as:

$Y≔X{\beta }^{\star }+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:

$\text{SNR}≔\frac{𝔼{\Vert X{\beta }^{\star }\Vert }_2^2}{𝔼{\Vert Z\Vert }_2^2}=\frac{ds}{p{\sigma }^2}.$

(6)

The maximum likelihood estimator (MLE) of ${\beta }^{\star }$ is defined by the random vector:

$\hat{\beta }≔{argmin}_{\beta \in {\{0,1\}}^p,{\Vert \beta \Vert }_0=s}{\Vert Y-X\beta \Vert }_2^2.$

(7)

We are interested in the minimum number of samples $n$ required so that the MLE (7) asymptotically recovers the true signal ${\beta }^{\star }$. Specifically: given an error tolerance $\delta \in (0,1)$, we wish to determine the minimum number of samples $n$ as a function of $p$, $s$ and $d$ required so that:

${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)⟶1,\text{as }n,p,s,d\to +\infty .$

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\to +\infty$, $d=o\left(p\right)$ and $ds=\omega \left(p\right)$ (i.e. $\text{SNR}\to +\infty$). Let $\delta \in (0,1)$. We consider two different regimes.

1. Assume $s=o\left(p\right)$. Let

   $n_{\text{SP}}^{\star }≔\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)+\log \left(\delta /\left(2{\sigma }^2\right)\right)}.$

   If there exists $\epsilon >0$ such that $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$, then the MLE $\hat{\beta }$ recovers ${\beta }^{\star }$ up to error $\delta$ w.h.p.:

   ${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)\ge 1-\exp \left(-\epsilon s\log \left(p/s\right)+o\left(s\log \left(p/s\right)\right)\right),$

   as $n,p,s,d\to +\infty$.

2. Assume there exists a constant $\alpha \in (0,1)$ such that $s=\alpha p$. Let:

   $n_{\text{SP}}^{\star }≔\frac{2h\left(\alpha \right)p}{\log d+\log \left(\delta \alpha /\left(2{\sigma }^2\right)\right)},$

   where $h(\cdot )$ denote the entropy function. If there exists $\epsilon >0$ such that $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$, then the MLE $\hat{\beta }$ recovers ${\beta }^{\star }$ up to error $\delta$ w.h.p.:

   ${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)\ge 1-\exp \left(-\epsilon h\left(\alpha \right)p+o\left(p\right)\right),$

   as $n,p,s,d\to +\infty$.

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^{\star }=\text{Supp}\left({\beta }^{\star }\right)$. For any $S\in 𝒮$, we denote by ${\mathrm{𝟙}}_S$ the vector in ${\left\{0,1\right\}}^p$ such that ${\left[{\mathrm{𝟙}}_S\right]}_i=\mathrm{𝟙}\left(i\in S\right)$ for all $i\in \left[p\right]$. We define the loss function $L$ over $𝒮$ such that $L\left(S\right)≔{\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2$, so that $\text{Supp}\left(\hat{\beta }\right)={argmin}_{S\in 𝒮}L\left(S\right)$. As $p$ gets large, the event “$L\left(S\right)<L\left(S^{\star }\right)$” for any $S$ such that $\left|S△S^{\star }\right|\ge 2\delta s$ is a rare event. The Chernoff bound yields:

$\log \mathbb{P}\left(L\left(S\right)<L\left(S^{\star }\right)\right)\le \frac{n}{2}\left(\log \left(\frac{2{\sigma }^{2}p}{\delta ds}\right)+o\left(1\right)\right).$

This step involves most of the technical work. Then, by union bound:

	$\mathbb{P}\left(\left|\text{Supp}\left(\hat{\beta }\right)△S^{\star }\right|<2\delta s\right)$	$\ge 1-\sum _{S:\left|S△S^{\star }\right|\ge 2\delta s}\mathbb{P}(L\left(S\right)<L\left(S^{\star }\right))$
		$\phantom{}\ge 1-\left(\frac{p}{s}\right){\left(\frac{2{\sigma }^{2}p}{\delta ds}\right)}^{n/2}.$

Solving for $n$, we obtain a critical threshold of $n^{\star }=\frac{2\log \left(\frac{p}{s}\right)}{\log \left(ds/p\right)+\log \left(\delta /\left(2{\sigma }^2\right)\right)}$. We conclude. ∎

Bringing together Theorem 1 with the necessary conditions shown by Wang et al. in [22], we obtain the following corollary.

Corollary 2 (Information-theoretic phase transition).

The sparse recovery in the sparse setting problem exhibits a phase transition at an information-theoretic threshold $n_{\text{INF}}^{\text{SP}}$.

1. In the first regime considered above, the expression of $n_{\text{INF}}^{\text{SP}}$ is given by:

   $n_{\text{INF}}^{\text{SP}}≔\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}.$

2. In the second regime considered above, the expression of $n_{\text{INF}}^{\text{SP}}$ is given by:

   $n_{\text{INF}}^{\text{SP}}≔\frac{2h\left(\alpha \right)p}{\log d}.$

Specifically, in each of these regimes:

• (i)

  If there exists $\epsilon >0$ such that $n\le \left(1-\epsilon \right)n_{\text{INF}}^{\text{SP}}$ then, as $n,p,s,d\to +\infty$, there exists no decoder $g:{ℝ}^n\to \{\beta \in {\{0,1\}}^p:{\Vert \beta \Vert }_0=s\}$ such that:

  $\underset{{\beta }^{\star }\in {\{0,1\}}^p,{\Vert {\beta }^{\star }\Vert }_0=s}{\max }{\mathbb{P}}_{X,Z}\left(g\left(Y\right)\ne \text{Supp}\left({\beta }^{\star }\right)\right)\to 0.$

  In this sense, it is information-theoretically impossible to ensure an asymptotically reliable recovery.

• (ii)

  If there exists $\epsilon >0$ such that $n\ge \left(1+\epsilon \right)n_{\text{INF}}^{\text{SP}}$, then as $n,p,s,d\to +\infty$:

  $\frac{\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|}{2s}⟶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\left(p\right)$. Previous works on sparse recovery in the dense case ([19],[9]) have shown the existence of an information-theoretic threshold:

  $n_{\text{INF}}=\frac{2s\log \left(p/s\right)}{\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\le \left(1-\epsilon \right)n_{\text{INF}}$, and full recovery is guaranteed by the MLE for $n\ge \left(1+\epsilon \right)n_{\text{INF}}$. 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:

  $n_{\text{INF}}^{\text{SP}}=\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}.$

  (9)

  In Table 1, we summarize these information-theoretic thresholds alongside known algorithmic thresholds for the sublinear sparsity regime $\left(s=o\left(p\right)\right)$, highlighting the comparison between dense and sparse measurements in the high-SNR setting.

  媒体内容 · 前往原文查看

  	Info-Theoretic		Algorithmic
  Measurement	Necessary	Sufficient	Necessary	Sufficient
  Dense	$\frac{2s\log \left(p/s\right)}{\log s}$ [19, 22]	$\frac{2s\log \left(p/s\right)}{\log s}$ [9, 19]	$2s\log \left(p-s\right)$ [9]	$2s\log \left(p-s\right)$ [21]
  Sparse, high SNR	$\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}$ [22]	$\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}$ (Thm 1)	Unknown	$2s\log \left(p-s\right)$ [18]†

  ^†Holds under the slow decay of sparsity assumption in [18], see (2).

• Price of Sparsity. In particular, we notice that $n_{\text{INF}}^{\text{SP}}\ge n_{\text{INF}}$. 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:

  $\Gamma ≔\frac{n_{\text{INF}}^{\text{SP}}}{n_{\text{INF}}}=\frac{\log s}{\log \left(ds/p\right)}>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 $\Gamma$. In particular, $\Gamma$ could take any value in $(1,+\infty )$, depending on the regimes of $d$ and $s$ w.r.t. $p$.

  Example 2.1.

  Consider the setting where $s=p^{\alpha }$, $d=p^{\beta }$ with $\alpha ,\beta \in (0,1)$ such that $\alpha +\beta >1$. Then $\Gamma =\alpha /\left(\alpha +\beta -1\right)\in (1,+\infty ),$ which approaches $1$ when $\beta$ approaches $1$ (low measurement sparsity), and approaches $+\infty$ when $\alpha$ is fixed and $\beta$ approaches $1-\alpha$ (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 $\phi \left(x\right)≔x/\log x$ for $x\ge e$. Consider two measurement matrices: $X_1$ a dense Gaussian in ${ℝ}^{n_1\times p}$ and $X_2$ a sparse Gaussian ${ℝ}^{n_2\times p}$ with only $d=\min (p^{o\left(1\right)},{\phi }^{-1}\left(o\left(\phi \left(p\right)\right)\right))$ expected non-zero entries per row; and an $s$-sparse signal ${\beta }^{\star }\in {ℝ}^p$, in the linear sparsity regime where $s=\alpha p$ for constant $\alpha \in (0,1)$. On the one hand, the number of samples required for reliable recovery raises from $n_1=n_{\text{INF}}=\Theta \left(p/\log p\right)$ in the dense case to $n_2=n_{\text{INF}}^{\text{SP}}=\Theta \left(p/\log d\right)$ 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 $n_{1}p=\Theta \left(p^2/\log p\right)$ to $n_{2}d=\Theta \left(pd/\log d\right)$. This highlights a trade-off between sampling complexity and computational cost. Namely, the sample-complexity ratio $n_2/n_1$ is at most logarithmic in $p$, while the computational gain $n_{1}p/\left(n_{2}d\right)$ 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 $\epsilon >0$ such that $n\ge \left(1+\epsilon \right)n_{\text{ALG}}$. As they show, this holds under the assumption that:

  ${\left(\frac{d}{p}\right)}^3\min \{s,\frac{\log \log \left(p-s\right)}{\log \left(p-s\right)}\}\to +\infty .$

  For example, when $s=\Theta \left(p\right)$, this requires that $d=\omega \left(p^{2/3}\right)$, while our result holds under the weaker assumption of $d=\omega \left(1\right)$. 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\in \mathbb{N}$ and ${\beta }^{\star }\in {\{0,1\}}^p$ $s$-sparse, defined as in Section 2.1. Let $X\in {ℝ}^{n\times p}$ such that ${\left(X_{i,j}\right)}_{i\in \left[n\right],j\in \left[p\right]}\stackrel{\text{i.i.d.}}{\sim }𝒩(0,1)$ and $Z\sim 𝒩(0,{\sigma }^2{I}_n)$, with $\sigma >0$ constant. Let $Y≔X{\beta }^{\star }+Z\in {ℝ}^n$. Let ${\left(B_{ij}\right)}_{i\in \left[n\right],j\in \left[p\right]}\stackrel{\text{i.i.d.}}{\sim }\text{Ber}\left(d/p\right)$. We define the following sparsified version of $X$:

$\tilde{X}\in {ℝ}^{n\times p}\text{such that}{\tilde{X}}_{ij}≔B_{ij}{X}_{ij},\forall i\in \left[n\right],j\in \left[p\right].$

(11)

In addition, we define a rescaled version of $Y$ as follows:

$\tilde{Y}≔\frac{d}{p}Y\in {ℝ}^n.$

(12)

An estimator of ${\beta }^{\star }$ is defined by the random vector:

$\hat{\beta }≔{argmin}_{\beta \in {\{0,1\}}^p,{\Vert \beta \Vert }_0=s}{\Vert \tilde{Y}-\tilde{X}\beta \Vert }_2^2.$

(13)

That is, the observations are generated with a dense measurement matrix ($X$), but the signal is recovered using a sparsification of that matrix ($\tilde{X}$). We formalize the problem we address below as follows: given an error tolerance $\delta \in (0,1)$, we wish to determine the minimum number of samples $n$ in terms of $p$, $s$ and $d$ required so that:

${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)⟶1,\text{as }n,p,s,d\to +\infty .$

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 $\alpha ,\delta \in (0,1)$. For every $\epsilon >0$, there exists ${\psi }_0={\psi }_0(\alpha ,\delta ,\epsilon )>0$ such that the following holds. Let $\psi \in (0,{\psi }_0)$ be fixed, and suppose that, as $p\to \infty$, $s=\alpha p$ and $d=\psi p$, up to harmless integer rounding. Let

$n_{\text{SP}}^{\star }≔\frac{2h\left(\alpha \right)p}{\log \left(1+\frac{\delta {\psi }^2}{\left(1-\psi \right)\left(2-\delta \left(1-\psi \right)\right)}\right)}.$

(14)

If $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$, then $\hat{\beta }$ recovers ${\beta }^{\star }$ up to error $\delta$ w.h.p.:

$\mathbb{P}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)⟶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 $\psi$, provided a large enough sample size.

• Strong-sparsification regime. In the strong-sparsification regime where $\psi \to 0$, the denominator of $n_{\text{SP}}^{\star }$ in (14) is effectively $\delta {\psi }^2/\left(2-\delta \right)$, and hence the sufficient condition upper bound writes:

  $n_{\text{INF}}^{\text{SP}}=\frac{2\left(2-\delta \right)h\left(\alpha \right)p}{\delta {\psi }^2}=\Theta \left(\frac{p}{{\psi }^2}\right).$

  (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:

  ${\Gamma }_{\text{Sparsification}}≔\frac{n_{\text{INF}}^{\text{SP}}}{n_{\text{INF}}}=\frac{\Theta \left(p/{\psi }^2\right)}{\Theta \left(p/\log p\right)}=\Theta \left(\frac{\log p}{{\psi }^2}\right).$

  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=\Theta \left(p\right)$, the price of sparsity is negligible, i.e. $\Gamma \to 1$. Instead, the price of sparsification is due to a bias in the observations that we explain by the fact that the sparsified observations $\tilde{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:

  ${\psi }_{\text{budget}}=\Theta \left(\sqrt{p/n}\right).$

  In particular, the above expression only makes sense when $n=\Omega \left(p\right)$, below which Theorem 3 does not hold.

4 Sparse Recovery using Sparse Measurements: Proofs

4.1 Proof of Theorem 1

For any $i\in \left[n\right]$, we denote by $X_i≔{\left(X_{ij}\right)}_{j\in \left[p\right]}$, $B_i≔{\left(B_{ij}\right)}_{j\in \left[p\right]}$, $N_i≔{\left(N_{ij}\right)}_{j\in \left[p\right]}$. We denote by $S^{\star }≔\text{Supp}\left({\beta }^{\star }\right)$ the support of ${\beta }^{\star }$. Let $𝒮≔\{S\subset \left[p\right]:\left|S\right|=s\}$. We define the function:

	$L:\phantom{}$	$𝒮⟶[0,+\infty )$
		$S⟼{\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2,$

where ${\mathrm{𝟙}}_S$ denotes the vector in ${\left\{0,1\right\}}^p$ such that ${\left[{\mathrm{𝟙}}_S\right]}_j=\mathrm{𝟙}\left(j\in S\right)$ for all $j\in \left[p\right]$. Note that, since $X$ and $Y$ are random, $L\left(S\right)$ is a random variable for every $S\in 𝒮$. In addition, note that:

$L\left(S\right)={\Vert Z\Vert }_2^2+{\Vert X\left({\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S\right)\Vert }_2^2+2⟨Z,X\left({\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S\right)⟩\forall S\in 𝒮,$

and, in particular:

$L\left(S^{\star }\right)={\Vert Z\Vert }_2^2=\sum _{i=1}^n{Z}_i^2.$

Fix $S\in 𝒮$ such that $M≔\left|S△S^{\star }\right|/2\ge \delta s$, and let $U≔S^{\star }\setminus S$, $V≔S\setminus S^{\star }$. Note that $\left|U\right|=\left|V\right|=M$. We define:

$\Delta ≔L\left(S\right)-L\left(S^{\star }\right).$

Proposition 4.1.

As $n,p,s,d\to +\infty$:

$\mathbb{P}\left(\Delta \le 0\right)\le {\left(\frac{2{\sigma }^{2}p}{\delta ds}\right)}^{n/2}{e}^{o\left(n\right)}.$

Proof. See section 4.1.3.

Hence, we obtain:

$\mathbb{P}\left({\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2\le {\Vert Y-X{\mathrm{𝟙}}_{S^{\star }}\Vert }_2^2\right)\le {\left(\frac{2{\sigma }^{2}p}{\delta ds}\right)}^{n/2}{e}^{o\left(n\right)},$

(16)

for any $S\in {\left\{0,1\right\}}^p$ such that $\left|S\right|=s$ and $\left|S△S^{\star }\right|\ge 2\delta s$.

Using (16) and the union bound over the set of supports $S\text{ s.t. }\left|S△S^{\star }\right|\ge 2\delta s$, we obtain:

		${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)$
		$\ge {\mathbb{P}}_{X,Z}({\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2>{\Vert Y-X{\mathrm{𝟙}}_{S^{\star }}\Vert }_2^2,\forall S:\left|S△S^{\star }\right|\ge 2\delta s)$
		$=1-{\mathbb{P}}_{X,Z}(\exists S:\left|S△S^{\star }\right|\ge 2\delta s,{\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2\le {\Vert Y-X{\mathrm{𝟙}}_{S^{\star }}\Vert }_2^2)$
		$\stackrel{\text{U.B.}}{\ge }1-\sum _{S:\left|S△S^{\star }\right|\ge 2\delta s}{\mathbb{P}}_{X,Z}({\Vert Y-X{\mathrm{𝟙}}_S\Vert }_2^2\le {\Vert Y-X{\mathrm{𝟙}}_{S^{\star }}\Vert }_2^2)$
		$\phantom{}\ge 1-\left(\frac{p}{s}\right){\left(\frac{2{\sigma }^{2}p}{\delta ds}\right)}^{n/2}{e}^{o\left(n\right)}.$

4.1.1 Sublinear regime: $s=o\left(p\right)$

Using the Corollary of Stirling:

$\log \left(\frac{p}{s}\right)=s\log \left(p/s\right)\left(1+o\left(1\right)\right),$

in the RHS of the inequality above, we obtain:

		${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)$
		$\phantom{}\ge 1-\exp \left[s\log \left(p/s\right)\left(1+o\left(1\right)\right)-\frac{n}{2}\left(\log \left(\frac{\delta ds}{2{\sigma }^{2}p}\right)+o\left(1\right)\right)\right].$

Let $n_{\text{SP}}^{\star }≔\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)+\log \left(\delta /\left(2{\sigma }^2\right)\right)}$. Then if $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$ for some constant $\epsilon >0$, we have:

		${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)$
		$\phantom{}\ge 1-\exp \left[s\log \left(p/s\right)\left(1+o\left(1\right)\right)-\frac{\left(1+\epsilon \right)n_{\text{SP}}^{\star }}{2}\left(\log \left(\frac{\delta ds}{2{\sigma }^{2}p}\right)+o\left(1\right)\right)\right]$
		$\phantom{}=1-\exp \left[s\log \left(p/s\right)\left(-\epsilon +o\left(1\right)-\frac{1+\epsilon }{\log \left(ds/p\right)+\log \left(\delta /\left(2{\sigma }^2\right)\right)}o\left(1\right)\right)\right]$
		$\phantom{}=1-\exp \left(s\log \left(p/s\right)\left(-\epsilon +o\left(1\right)\right)\right).$

Hence, as $n,p,s,d\to +\infty$:

${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)\ge 1-\exp \left(-\epsilon s\log \left(p/s\right)+o\left(s\log \left(p/s\right)\right)\right)⟶1.$

4.1.2 Linear regime: $s=\alpha p$ , $\alpha \in (0,1)$

Using the Corollary of Stirling:

$\log \left(\frac{p}{s}\right)=ph\left(\alpha \right)\left(1+o\left(1\right)\right),$

we get:

		${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)$
		$\phantom{}\ge 1-\exp \left[ph\left(\alpha \right)\left(1+o\left(1\right)\right)-\frac{n}{2}\left(\log \left(\frac{\delta ds}{2{\sigma }^{2}p}\right)+o\left(1\right)\right)\right].$

Similarly to above, we take $n_{\text{SP}}^{\star }≔\frac{2h\left(\alpha \right)p}{\log d+\log \left(\delta \alpha /\left(2{\sigma }^2\right)\right)}$. If $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$ for some constant $\epsilon >0$, then we obtain, as $p,s,d\to +\infty$:

${\mathbb{P}}_{X,Z}\left(\left|\text{Supp}\left({\beta }^{\star }\right)△\text{Supp}\left(\hat{\beta }\right)\right|<2\delta s\right)\ge 1-\exp \left(-\epsilon h\left(\alpha \right)p+o\left(p\right)\right)⟶1,$

concluding the proof. ∎

4.1.3 Proof of Proposition 4.1

We have:

	$\Delta$	$\phantom{}≔L\left(S\right)-L\left(S^{\star }\right)$
		$\phantom{}={\Vert X\left({\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S\right)\Vert }_2^2+2⟨Z,X\left({\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S\right)⟩$
		$\phantom{}=\sum _{i=1}^n{⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2+2\sum _{i=1}^n{Z}_i⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩.$

We denote by ${\left({\Delta }_i\right)}_{i\in \left[n\right]}$ the terms of the sum in the above expression, that is:

${\Delta }_i≔{⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2+2Z_i⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩.$

Note that ${\left({\Delta }_i\right)}_{i\in \left[n\right]}$ are i.i.d. and $\Delta ={\sum }_{i=1}^n{\Delta }_i$.

Now using the Chernoff bound:

$\mathbb{P}\left(\Delta \le 0\right)=\mathbb{P}\left(-\Delta \ge 0\right)=\underset{\theta \ge 0}{inf}\mathbb{P}\left(e^{-\theta \Delta }\ge 1\right)\le \underset{\theta \ge 0}{inf}{M}_{-{\Delta }_i}{\left(\theta \right)}^n.$

(17)

We now study the moment generating function of $-{\Delta }_i$, i.e. $M_{-{\Delta }_i}(\cdot )$. We have:

	$M_{-{\Delta }_i}\left(\theta \right)$	$\phantom{}={𝔼}_{X_i,Z_i}\left[e^{-\theta \left[{⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2+2Z_i⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩\right]}\right]$
		$\phantom{}={𝔼}_{X_i}\left[e^{-\theta {⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2}{𝔼}_{Z_i}\left[e^{-2\theta Z_i⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}|X_i\right]\right]$
		$\phantom{}={𝔼}_{X_i}\left[e^{-\theta {⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2}{M}_{Z_i|X_i}\left(-2\theta ⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩\right)\right]$
		$\phantom{}={𝔼}_{X_i}\left[e^{-\theta {⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2}{e}^{\frac{1}{2}{\left(-2\theta ⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩\right)}^2{\sigma }^2}\right]$
		$\phantom{}={𝔼}_{X_i}\left[e^{\left(-\theta +2{\theta }^2{\sigma }^2\right){⟨X_i,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩}^2}\right]$
		$\phantom{}={𝔼}_{X_i}\left[e^{\left(-\theta +2{\theta }^2{\sigma }^2\right){\left({\sum }_{j\in U}{X}_{ij}-{\sum }_{j\in V}{X}_{ij}\right)}^2}\right].$

Plugging this expression into (17), we obtain:

$\log \mathbb{P}\left(\Delta \le 0\right)\le n\underset{\theta \ge 0}{inf}\log {𝔼}_{X_i}\left[e^{\left(-\theta +2{\theta }^2{\sigma }^2\right){\left({\sum }_{j\in U}{X}_{ij}-{\sum }_{j\in V}{X}_{ij}\right)}^2}\right].$

Studying the function $\theta \mapsto -\theta +2{\theta }^2{\sigma }^2$ on ${ℝ}_{\phantom{}\ge 0}$ leads to the change of variable:

		$\underset{\theta \ge 0}{inf}\log {𝔼}_{X_i}\left[e^{\left(-\theta +2{\theta }^2{\sigma }^2\right){\left({\sum }_{j\in U}{X}_{ij}-{\sum }_{j\in V}{X}_{ij}\right)}^2}\right]$		(18)
		$=\underset{\theta \in (-\infty ,1/(8\sigma {}^2\left)\right]}{inf}\log {𝔼}_{X_i}\left[e^{-\theta {\left({\sum }_{j\in U}{X}_{ij}-{\sum }_{j\in V}{X}_{ij}\right)}^2}\right],$		(19)

One can check that the function $\theta \mapsto \log {𝔼}_{X_i}\left[e^{-\theta {\left({\sum }_{j\in U}{X}_{ij}-{\sum }_{j\in V}{X}_{ij}\right)}^2}\right]$ is non-increasing over $(-\infty ,1/\left(8{\sigma }^2\right)]$. Hence (19) is equal to:

$\log {𝔼}_{X_i}\left[e^{-(\sum {}_{j\in U}X{}_{ij}-\sum {}_{j\in V}X{}_{ij}){}^2/\left(8\sigma {}^2\right)}\right].$

Therefore, the Chernoff bound yields:

$\log \mathbb{P}(\Delta \le 0)\le n\log {𝔼}_{X_i}\left[e^{-(\sum {}_{j\in U}X{}_{ij}-\sum {}_{j\in V}X{}_{ij}){}^2/\left(8\sigma {}^2\right)}\right].$

(20)

Since $U\cap V=\varnothing$, we have:

$\sum _{j\in U}{X}_{ij}-\sum _{j\in V}{X}_{ij}\stackrel{d}{=}\sum _{j\in U\cup V}{X}_{ij}.$

Therefore:

	$𝔼\left[e^{-(\sum {}_{j\in U}X{}_{ij}-\sum {}_{j\in V}X{}_{ij}){}^2/\left(8\sigma {}^2\right)}\right]$	$=𝔼\left[e^{-\left(\sum {}_{j\in U\cup V}X{}_{ij}\right){}^2/\left(8\sigma {}^2\right)}\right]$
		$=𝔼\left[e^{-\left(\sum {}_{j\in U\cup V}B{}_{ij}N{}_{ij}\right){}^2/\left(8\sigma {}^2\right)}\right]$
		$={𝔼}_{B_i}\left[{𝔼}_{N_i}\left[e^{-\left(\sum {}_{j\in U\cup V}B{}_{ij}N{}_{ij}\right){}^2/\left(8\sigma {}^2\right)}\right|B_i]\right]$
		$={𝔼}_{B_i}\left[{𝔼}_{N_i}\left[e^{-\left(\frac{{\sum }_{j\in U\cup V}{B}_{ij}{N}_{ij}}{\sqrt{{\sum }_{j\in U\cup V}{B}_{ij}}}\right){}^2\times \frac{{\sum }_{j\in U\cup V}{B}_{ij}}{8{\sigma }^2}}\right|B_i]\right].$

In addition, conditionally on $B_i$, we have:

$Q≔{\left(\frac{{\sum }_{j\in U\cup V}{B}_{ij}{N}_{ij}}{\sqrt{{\sum }_{j\in U\cup V}{B}_{ij}}}\right)}^2\stackrel{d}{=}{\chi }^2\left(1\right).$

Its MGF is:

$𝔼\left[e^{tQ}|B_i\right]=M_{Q|B_i}\left(t\right)=\frac{1}{\sqrt{1-2t}},\text{ for }t<1/2.$

Hence:

	${𝔼}_{B_i}\left[{𝔼}_{N_i}\left[e^{-\left(\frac{{\sum }_{j\in U\cup V}{B}_{ij}{N}_{ij}}{\sqrt{{\sum }_{j\in U\cup V}{B}_{ij}}}\right){}^2\times \frac{{\sum }_{j\in U\cup V}{B}_{ij}}{8{\sigma }^2}}\right|B_i]\right]$	$\phantom{}={𝔼}_{B_i}\left[M_{Q|B_i}\left(-\frac{{\sum }_{j\in U\cup V}{B}_{ij}}{8{\sigma }^2}\right)\right]$
		$\phantom{}={𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U\cup V}{B}_{ij}}}\right].$

Let $U_{\left[\delta s\right]}$ and $V_{\left[\delta s\right]}$ respectively denote the sets of $\delta s$ smallest elements of $U$ and $V$. Note that this definition is legitimate since $\left|U\right|=\left|V\right|=M\ge \delta s$. Since $B_{ij}\ge 0$ for all $j\in U\cup V$, we have:

$\sum _{j\in U\cup V}{B}_{ij}\ge \sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij},$

and hence:

${𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U\cup V}{B}_{ij}}}\right]\le {𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}\right].$

Therefore, we get:

$𝔼\left[e^{-(\sum {}_{j\in U}X{}_{ij}-\sum {}_{j\in V}X{}_{ij}){}^2/\left(8\sigma {}^2\right)}\right]\le {𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}\right],$

and plugging this into (20) yields:

$\log \mathbb{P}\left(\Delta \le 0\right)\le n\log \left({𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}\right]\right).$

(21)

Now note that, for any $i\in \left[n\right]$:

$\sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}\stackrel{d}{=}\text{Bin}(2\delta s,\frac{d}{p}),$

In addition, since $d=o\left(p\right)$ and $ds/p\to +\infty$, we have:

Lemma 4.1.

For any $i\in \left[n\right]$, the following holds: as $p\to +\infty$,

$\frac{1}{\sqrt{2\delta ds/p}}\left(\sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}-2\delta ds/p\right)\stackrel{\text{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

$N_p≔\frac{1}{\sqrt{2\delta ds/p}}\left(\sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}-2\delta ds/p\right),$

which is exactly the quantity appearing in Lemma 4.1, so that $N_p\stackrel{\text{dist}}{⟶}𝒩(0,1)$ and in particular $N_p=O\left(1\right)$. By construction,

$\sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}=2\delta ds/p+\sqrt{2\delta ds/p}{N}_p,$

with no remainder term, so that

$V_p≔\frac{2\sigma \sqrt{ds/p}}{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}=\frac{2\sigma }{\sqrt{2\delta +\frac{4{\sigma }^2}{ds/p}+\sqrt{\frac{2\delta }{ds/p}}{N}_p}}.$

Since $ds/p\to +\infty$ and $N_p=O\left(1\right)$, the last two terms under the root vanish in probability, hence

$V_p\stackrel{\mathbb{P}}{⟶}\frac{2\sigma }{\sqrt{2\delta }}=\sqrt{\frac{2{\sigma }^2}{\delta }}.$

In addition, we note the following:

Lemma 4.2.

$V_p$ is uniformly integrable, that is: there exists $p^{\prime }\in \mathbb{N}$ such that

$\underset{T\to +\infty }{lim}\underset{p\ge p^{\prime }}{sup}𝔼\left[\left|V_p\right|{\mathrm{𝟙}}_{\left\{\right|V{}_p|>T\}}\right]=0.$

Proof. See appendix A.1.2.

Since $V_p\stackrel{\mathbb{P}}{⟶}\sqrt{2{\sigma }^2/\delta }$ and ${\left(V_p\right)}_p$ is uniformly integrable, the convergence holds in $L^1$; therefore

$\underset{p\to +\infty }{lim}𝔼\left[V_p\right]=\sqrt{\frac{2{\sigma }^2}{\delta }}.$

Hence, we write:

${𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}\right]=\sqrt{\frac{2{\sigma }^{2}p}{\delta ds}}+o\left({\left(\frac{ds}{p}\right)}^{-1/2}\right).$

We conclude:

	$\log \mathbb{P}\left(\Delta \le 0\right)$	$\phantom{}\le n\log \left({𝔼}_{B_i}\left[\frac{2\sigma }{\sqrt{4{\sigma }^2+{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}}}\right]\right)$
		$=n\log (\sqrt{\frac{2{\sigma }^{2}p}{\delta ds}}+o\left({\left(\frac{ds}{p}\right)}^{-1/2}\right))$
		$\phantom{}=n\left(\log \left(\sqrt{\frac{2{\sigma }^{2}p}{\delta ds}}\right)+\log \left(1+o\left(1\right)\right)\right)$
		$\phantom{}=n\left(\log \left(\sqrt{\frac{2{\sigma }^{2}p}{\delta ds}}\right)+o\left(1\right)\right)$
		$\phantom{}=n\log \left(\sqrt{\frac{2{\sigma }^{2}p}{\delta ds}}\right)+o\left(n\right),$

which yields the desired result:

$\mathbb{P}\left(\Delta \le 0\right)\le {\left(\frac{2{\sigma }^{2}p}{\delta ds}\right)}^{n/2}{e}^{o\left(n\right)}.$

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\in {ℝ}^{n\times p}$ be drawn with i.i.d. elements from the following distribution:

$X_{ij}=\{\begin{array}{cc}𝒩(0,\frac{1}{\gamma }),& \text{w.p. }\gamma \\ 0,& \text{w.p. }1-\gamma \end{array},\text{ for all }i\in \left[n\right],j\in \left[p\right];$

(22)

where $\gamma \in (0,1]$. Let $\lambda >0$ and

${𝒞}_{p,s}\left(\lambda \right)≔\{\beta \in {ℝ}^p|\left|\text{Supp}\left(\beta \right)\right|=s,\underset{i\in \text{Supp}\left(\beta \right)}{\min }\left|{\beta }_i\right|=\lambda \}.$

Assume that ${\sigma }^2=1$. Then, in the regime where $\gamma s\to +\infty$, a necessary condition for asymptotically reliable recovery over the signal class ${𝒞}_{p,s}\left(\lambda \right)$ is given by:

$n>\frac{\log \left(\frac{p}{s}\right)-1}{\frac{1}{2}\log \left(1+s{\lambda }^2\right)}.$

While Theorem 4 is not stated on the exact same signal space ${𝒞}_{p,s}\left(\lambda \right)$ in [22] but rather on the larger:

$\{\beta \in {ℝ}^p|\left|\text{Supp}\left(\beta \right)\right|=s,\underset{i\in \text{Supp}\left(\beta \right)}{\min }\left|{\beta }_i\right|\ge \lambda \},$

it follows directly from their result on “restricted ensembles” where the signal components under consideration are set exactly to $\lambda$ (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/\sqrt{\gamma }$, and require that the noise variance is ${\sigma }^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\sim 𝒩(0,{\sigma }^2{I}_n)$, can be equivalently written as:

$Y_0=X_0{\beta }_0^{\star }+Z_0,$

$Y_0≔\frac{1}{\sigma }Y,X_0≔\frac{1}{\sqrt{d/p}}X,{\beta }_0^{\star }≔\frac{\sqrt{d/p}}{\sigma }{\beta }^{\star },\text{and}{Z}_0≔\frac{1}{\sigma }Z\sim 𝒩(0,I_n).$

Hence, it is a particular case of the model defined in (22), with:

$\gamma ≔d/p\text{and}\lambda ≔\frac{\sqrt{\gamma }}{\sigma }.$

In addition, the regime we consider of $d=\omega \left(p/s\right)$ corresponds exactly to the regime considered in Theorem 4 where $\gamma s\to +\infty$. Therefore, using Theorem 4, a necessary condition for an asymptotically reliable recovery of ${\beta }^{\star }$ in the considered regime is given by:

$n>\frac{\log \left(\frac{p}{s}\right)-1}{\frac{1}{2}\log \left(1+s{\lambda }^2\right)}=\frac{2\log \left(\frac{p}{s}\right)-2}{\log \left(1+ds/\left(p{\sigma }^2\right)\right)}=\frac{2\log \left(\frac{p}{s}\right)}{\log \left(ds/p\right)}\left(1+o\left(1\right)\right).$

(23)

4.2.1.1 Sublinear regime: $s=o\left(p\right)$

Using the Corollary of Stirling:

$\log \left(\frac{p}{s}\right)=s\log \left(p/s\right)\left(1+o\left(1\right)\right),$

the necessary condition (23) writes:

$n>\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}\left(1+o\left(1\right)\right).$

$n_{\text{INF}}^{\text{SP}}≔\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}.$

Assume there exists $\epsilon >0$ such that $n\le \left(1-\epsilon \right)n_{\text{INF}}^{\text{SP}}$. We know that, for large enough $n,p,s,d$ we have:

$n\le \left(1-\epsilon \right)n_{\text{INF}}^{\text{SP}}<\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}\left(1+o\left(1\right)\right),$

which contradicts the necessary condition. Therefore, it is information-theoretically impossible to ensure a reliable recovery of the support of ${\beta }^{\star }$.

4.2.1.2 Linear regime: $s=\alpha p,\alpha \in (0,1)$.

Using the Corollary of Stirling:

$\log \left(\frac{p}{s}\right)=ph\left(\alpha \right)\left(1+o\left(1\right)\right),$

the necessary condition (23) writes:

$n>\frac{2h\left(\alpha \right)p}{\log d}\left(1+o\left(1\right)\right).$

$n_{\text{INF}}^{\text{SP}}≔\frac{2h\left(\alpha \right)p}{\log d}.$

Similarly to above, we conclude that if there exists $\epsilon >0$ such that $n\le \left(1-\epsilon \right)n_{\text{INF}}^{\text{SP}}$ then it is information-theoretically impossible to ensure a reliable recovery of the support of ${\beta }^{\star }$.

4.2.2 Sufficient condition

We show that (ii) holds using Theorem 1.

4.2.2.1 Sublinear regime: $s=o\left(p\right)$.

Let $\delta >0$ and:

$n_{\text{SP}}^{\star }≔\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)+\log \left(\delta /\left(2{\sigma }^2\right)\right)}.$

Note that:

$n_{\text{INF}}^{\text{SP}}=\frac{2s\log \left(p/s\right)}{\log \left(ds/p\right)}=n_{\text{SP}}^{\star }\left(1+o\left(1\right)\right).$

Assume there exists $\epsilon$ such that $n\ge \left(1+\epsilon \right)n_{\text{INF}}^{\text{SP}}$. Then:

$n\ge \left(1+\epsilon \right)\left(1+o\left(1\right)\right)n_{\text{SP}}^{\star }=\left(1+\epsilon +o\left(1\right)\right)n_{\text{SP}}^{\star }\ge \left(1+\epsilon /2\right)n_{\text{SP}}^{\star },$

for $n,p,s,d$ large enough. Using Theorem 1, we have:

${\mathbb{P}}_{X,Z}\left(\frac{1}{2s}\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|<\delta \right)\ge 1-\exp \left(-\epsilon s\log \left(p/s\right)+o\left(s\log \left(p/s\right)\right)\right).$

Therefore, we obtain:

${\mathbb{P}}_{X,Z}\left(\frac{1}{2s}\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|<\delta \right)⟶1,$

as $n,p,s,d\to +\infty$. Since this holds for all $\delta >0$, we conclude:

$\frac{\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|}{2s}⟶0,$

in probability, as $n,p,s,d\to +\infty$.

4.2.2.2 Linear regime: $s=\alpha p,\alpha \in (0,1)$.

Let $\delta >0$ and:

$n_{\text{SP}}^{\star }≔\frac{2h\left(\alpha \right)p}{\log d+\log \left(\delta \alpha /\left(2{\sigma }^2\right)\right)}.$

Note that:

$n_{\text{INF}}^{\text{SP}}=\frac{2h\left(\alpha \right)p}{\log d}=n_{\text{SP}}^{\star }\left(1+o\left(1\right)\right).$

Assume there exists $\epsilon$ such that $n\ge \left(1+\epsilon \right)n_{\text{INF}}^{\text{SP}}$. Then:

$n\ge \left(1+\epsilon \right)\left(1+o\left(1\right)\right)n_{\text{SP}}^{\star }=\left(1+\epsilon +o\left(1\right)\right)n_{\text{SP}}^{\star }\ge \left(1+\epsilon /2\right)n_{\text{SP}}^{\star },$

for $n,p,s,d$ large enough. Using Theorem 1, we have:

${\mathbb{P}}_{X,Z}\left(\frac{1}{2s}\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|<\delta \right)\ge 1-\exp \left(-\epsilon h\left(\alpha \right)p+o\left(p\right)\right).$

Therefore, we obtain:

${\mathbb{P}}_{X,Z}\left(\frac{1}{2s}\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|<\delta \right)⟶1,$

as $n,p,s,d\to +\infty$. Since this holds for all $\delta >0$, we conclude:

$\frac{\left|\text{Supp}\left(\hat{\beta }\right)△\text{Supp}\left({\beta }^{\star }\right)\right|}{2s}⟶0,$

in probability, as $n,p,s,d\to +\infty$. ∎

4.3 Proof of Example 2.2

We have $d=\min (p^{o\left(1\right)},{\phi }^{-1}\left(o\left(\phi \left(p\right)\right)\right))$, hence:

$\{\begin{array}{cc}\log d/\log p=o\left(1\right)& \\ \phi \left(d\right)/\phi \left(p\right)=o\left(1\right)& \end{array}.$

In addition:

$n_1=n_{\text{INF}}=\Theta \left(p/\log p\right),n_2=n_{\text{INF}}^{\text{SP}}=\Theta \left(p/\log d\right).$

Therefore, we have:

$\frac{n_2}{n_1}=\frac{\Theta \left(p/\log d\right)}{\Theta \left(p/\log p\right)}=\Theta \left(\frac{\log p}{\log d}\right)=\omega \left(1\right),$

On one hand, the number of samples required for reliable recovery is better in the dense case:

$n_1=\Theta \left(p/\log p\right)=o\left(p/\log d\right)=o\left(n_2\right).$

(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 $X_1$ with a vector in ${ℝ}^p$ costs:

$n_{1}p=\Theta \left(p^2/\log p\right)$

real number multiplications, while multiplying $X_2$ with a vector in ${ℝ}^p$ costs

$n_{2}d=\Theta \left(pd/\log d\right)=p\Theta \left(\phi \left(d\right)\right)=po\left(\phi \left(p\right)\right)=o\left(p^2/\log p\right)=o\left(n_{1}p\right),$

(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 $\alpha p$ and $\psi p$ are integers; since standard rounding only affects lower-order terms.

Let $S^{\star }≔\text{Supp}\left({\beta }^{\star }\right)$ and let

$𝒮≔\{S\subset \left[p\right]:\left|S\right|=s\}.$

For $S\in 𝒮$, define

$L\left(S\right)≔{\Vert \tilde{Y}-\tilde{X}{\mathrm{𝟙}}_S\Vert }_2^2.$

For a competing support $S$, write

$A=A\left(S\right)≔S^{\star }\setminus S,B=B\left(S\right)≔S\setminus S^{\star },C=C\left(S\right)≔S^{\star }\cap S,$

and let

$M=M\left(S\right)≔\left|A\right|=\left|B\right|=\frac{1}{2}\left|S△S^{\star }\right|.$

We put $\eta ≔M/s\in \left[0,1\right]$. For a fixed support $S$, set

${\Delta }_S≔L\left(S\right)-L\left(S^{\star }\right).$

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 ${\Delta }_S$, followed by a union bound over supports $S$ with $\left|S△S^{\star }\right|\ge 2\delta s$. The technical work, however, is substantially more involved, because $\tilde{Y}$ is not a noisy projection of the true signal through $\tilde{X}$ but a rescaling of the original observations $Y$. As a result, ${\Delta }_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 $B_1$.

The strategy is to compute the row MGF conditionally on $B_1$. After integrating out the noise $Z_1$, the conditional MGF takes the form $𝔼\left[\exp \left(U_{\theta }{V}_{\theta }\right)\mid B_1\right]$ for a centered Gaussian pair $(U_{\theta },V_{\theta })$ whose variances and covariance are explicit polynomials in the mask sums $x_A\left(B_1\right),x_B\left(B_1\right),x_C\left(B_1\right)$ over the index sets $A,B,C$ defined above (Lemma 5.1). This expression is finite only when a discriminant $D_p(\theta ,b)={\left(1-c_p(\theta ,b)\right)}^2-a_p(\theta ,b)b_p(\theta ,b)$ is positive.

A natural choice of Chernoff parameter ${\theta }^{\star }$ 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 $\eta {\psi }^2$ and $2-\eta -2\psi \left(1-\eta \right)$ terms combine into $-T_{\eta }$). The drawback is that $D_p({\theta }^{\star },b)$ vanishes on a set of masks $b$ of exponentially small probability, so directly evaluating the bound at ${\theta }^{\star }$ would require a uniform-integrability hypothesis to justify passing to the limit. We sidestep this by evaluating the Chernoff bound at the shrunken parameter ${\theta }_{p,\lambda }≔\lambda {\theta }^{\star }$ for some fixed $\lambda \in (0,1)$. The factor $\lambda <1$ keeps $D_p({\theta }_{p,\lambda },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\lambda -{\lambda }^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\lambda -{\lambda }^2\to 1$ as $\lambda \to 1^{-}$, the slack $\epsilon$ 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 $\delta$.

Proposition 5.1.

Fix $\alpha ,\delta \in (0,1)$ and $\lambda \in (0,1)$. There exists ${\psi }_0={\psi }_0(\alpha ,\delta ,\lambda )>0$ such that, for every fixed $\psi \in (0,{\psi }_0)$, uniformly over all $S\in 𝒮$ with $\eta ≔M\left(S\right)/s\ge \delta$,

$\mathbb{P}({\Delta }_S\le 0)\le {(1+(2\lambda -{\lambda }^2)\eta \psi C^{\star }\left(\eta \right))}^{-n/2}{e}^{o\left(n\right)},$

(26)

$C^{\star }\left(\eta \right)≔\frac{\psi }{\left(1-\psi \right)\left(2-\eta \left(1-\psi \right)\right)}.$

(27)

The $o\left(n\right)$ term is uniform in $S$ and in $\eta \in \left[\delta ,1\right]$.

Before proving Proposition 5.1, we show how it implies Theorem 3.

Fix $\epsilon >0$. We construct $\lambda$ and ${\psi }_0$ below; $\lambda$ will depend only on $\epsilon$ and ${\psi }_0$ only on $(\alpha ,\delta ,\lambda )$, so the resulting ${\psi }_0$ depends only on $(\alpha ,\delta ,\epsilon )$, as the statement requires.

Step 1: choose $\lambda$. Pick $\lambda \in (0,1)$ sufficiently close to one so that

$\left(1+\epsilon \right)\left(2\lambda -{\lambda }^2\right)>1.$

(28)

Such $\lambda$ clearly exists.

Step 2: choose ${\psi }_0$. The function $g\left(x\right)≔\left(1+\epsilon \right)\log \left(1+\left(2\lambda -{\lambda }^2\right)x\right)-\log \left(1+x\right)$ satisfies $g\left(0\right)=0$ and for any $x\ge 0$ we have by (28):

$g^{\prime }\left(x\right)=\frac{\left(1+\epsilon \right)\left(2\lambda -{\lambda }^2\right)}{1+\left(2\lambda -{\lambda }^2\right)x}-\frac{1}{1+x}>0,$

therefore $g\left(x\right)>0$ for all $x\ge 0$. Hence, for every $\psi \in (0,1)$ we have:

$\left(1+\epsilon \right)\log \left(1+\left(2\lambda -{\lambda }^2\right)\delta \psi C^{\star }\left(\delta \right)\right)>\log \left(1+\delta \psi C^{\star }\left(\delta \right)\right).$

(29)

Let ${\psi }_0$ be the threshold supplied by Proposition 5.1 for the chosen $\lambda$. Fix any $\psi \in (0,{\psi }_0)$ and assume $n\ge \left(1+\epsilon \right)n_{\text{SP}}^{\star }$.

Step 3: union bound. By Proposition 5.1, for every support $S$ with $M\left(S\right)\ge \delta s$,

$\mathbb{P}({\Delta }_S\le 0)\le {(1+(2\lambda -{\lambda }^2)\eta \psi C^{\star }\left(\eta \right))}^{-n/2}{e}^{o\left(n\right)}.$

The function

$\eta ⟼\eta C^{\star }\left(\eta \right)=\frac{\eta \psi }{\left(1-\psi \right)\left(2-\eta \left(1-\psi \right)\right)}$

is increasing on $[0,1]$. Hence, for $\eta \ge \delta$:

$\mathbb{P}({\Delta }_S\le 0)\le {(1+(2\lambda -{\lambda }^2)\delta \psi C^{\star }\left(\delta \right))}^{-n/2}{e}^{o\left(n\right)}.$

Using the union bound over all supports of cardinality $s$,

		$\mathbb{P}\left(\left|\text{Supp}\left(\hat{\beta }\right)△S^{\star }\right|\ge 2\delta s\right)$
		$\le \sum _{S\in 𝒮:M\left(S\right)\ge \delta s}\mathbb{P}({\Delta }_S\le 0)$
		$\le \left(\frac{p}{s}\right){(1+(2\lambda -{\lambda }^2)\delta \psi C^{\star }\left(\delta \right))}^{-n/2}{e}^{o\left(n\right)}.$

Since $s=\alpha p$, Stirling’s formula gives $\log \left(\frac{p}{s}\right)=h\left(\alpha \right)p+o\left(p\right)$. Moreover, by the definition of $n_{\text{SP}}^{\star }$,

$h\left(\alpha \right)p=\frac{n_{\text{SP}}^{\star }}{2}\log \left(1+\delta \psi C^{\star }\left(\delta \right)\right).$

Note that $o\left(p\right)=o\left(n\right)$ since $n=\Theta \left(p\right)$ for fixed $\psi$. Therefore

	$\log \mathbb{P}\left(\left|\text{Supp}\left(\hat{\beta }\right)△S^{\star }\right|\ge 2\delta s\right)$	$\phantom{}\le h\left(\alpha \right)p-\frac{n}{2}\log \left(1+\left(2\lambda -{\lambda }^2\right)\delta \psi C^{\star }\left(\delta \right)\right)+o\left(n\right)$
		$\le \frac{n_{\text{SP}}^{\star }}{2}[\log (1+\delta \psi C^{\star }\left(\delta \right))$
		$-(1+\epsilon )\log (1+(2\lambda -{\lambda }^2)\delta \psi C^{\star }\left(\delta \right))]+o(n).$

By (29), the bracketed term is a strictly negative constant. Since $n_{\text{SP}}^{\star }=\Theta \left(p\right)$ for fixed $\psi$, the right-hand side tends to $-\infty$. This proves

$\mathbb{P}\left(\left|\text{Supp}\left(\hat{\beta }\right)△S^{\star }\right|<2\delta s\right)⟶1.$

It remains to prove Proposition 5.1.

5.1 Conditional Chernoff transform

Fix $S\in 𝒮$ and write $A,B,C,M,\eta$ as above. We have:

	${\Delta }_S$	$\phantom{}=L\left(S\right)-L\left(S^{\star }\right)$
		$\phantom{}={\Vert \frac{d}{p}X{\mathrm{𝟙}}_{S^{\star }}-\tilde{X}{\mathrm{𝟙}}_S+\frac{d}{p}Z\Vert }_2^2-{\Vert \left(\frac{d}{p}X-\tilde{X}\right){\mathrm{𝟙}}_{S^{\star }}+\frac{d}{p}Z\Vert }_2^2$
		$\phantom{}={\Vert \tilde{X}{\mathrm{𝟙}}_S\Vert }_2^2-{\Vert \tilde{X}{\mathrm{𝟙}}_{S^{\star }}\Vert }_2^2+2\frac{d}{p}⟨X{\mathrm{𝟙}}_{S^{\star }}+Z,\tilde{X}\left({\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S\right)⟩$
		$\phantom{}=\sum _{i=1}^n{⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩}^2-\sum _{i=1}^n{⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩}^2+2\frac{d}{p}\sum _{i=1}^n\left(⟨X_i,{\mathrm{𝟙}}_{S^{\star }}⟩+Z_i\right)\left(⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩-⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩\right)$
		$\phantom{}=\sum _{i=1}^n\left({⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩}^2-{⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩}^2+2\psi \left(⟨X_i,{\mathrm{𝟙}}_{S^{\star }}⟩+Z_i\right)\left(⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩-⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩\right)\right).$

For each row $i$, let

${\Delta }_i≔{⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩}^2-{⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩}^2+2\psi \left(⟨X_i,{\mathrm{𝟙}}_{S^{\star }}⟩+Z_i\right)\left(⟨{\tilde{X}}_i,{\mathrm{𝟙}}_{S^{\star }}⟩-⟨{\tilde{X}}_i,{\mathrm{𝟙}}_S⟩\right).$

Then ${\Delta }_S={\sum }_{i=1}^n{\Delta }_i$, and the ${\Delta }_i$’s are i.i.d. For $\theta >0$, Chernoff’s bound gives

$\mathbb{P}\left({\Delta }_S\le 0\right)\le {\left(𝔼\left[e^{-\theta {\Delta }_1}\right]\right)}^n,$

(30)

for all $\theta >0$. We compute the row moment generating function. Let $B_1={\left(B_{1j}\right)}_{j\in \left[p\right]}$ be the first row of the sparsification mask. Conditionally on $B_1$, integrating first over $Z_1\sim 𝒩(0,{\sigma }^2)$ yields

$𝔼\left[e^{-\theta {\Delta }_1}\mid B_1\right]=𝔼\left[e^{U_{\theta }{V}_{\theta }}\mid B_1\right],$

(31)

where we define the centered jointly Gaussian variables

	$U_{\theta }$	$\phantom{}≔\theta \left(\sum _{j\in A}{B}_{1j}{X}_{1j}-\sum _{j\in B}{B}_{1j}{X}_{1j}\right),$
	$V_{\theta }$	$\phantom{}≔\sum _{j\in A}\left(\left(1+\gamma \left(\theta \right)\right)B_{1j}-2\psi \right)X_{1j}+\sum _{j\in B}\left(1-\gamma \left(\theta \right)\right)B_{1j}{X}_{1j}$
		$+2\sum _{j\in C}(B_{1j}-\psi )X_{1j},$

$\gamma \left(\theta \right)≔2{\psi }^2{\sigma }^2\theta .$

(32)

The identity (31), with the stated forms of $U_{\theta }$ and $V_{\theta }$, follows from a direct expansion of ${\Delta }_1$ and a Gaussian integration over $Z_1$; 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≔\mathrm{Var}\left(U\right),b≔\mathrm{Var}\left(V\right),c≔\mathrm{Cov}(U,V).$

$D≔{\left(1-c\right)}^2-ab>0,$

$𝔼\left[e^{UV}\right]=D^{-1/2}.$

If $D\le 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={\left(b_j\right)}_{j\in \left[p\right]}\in {\{0,1\}}^p$, define

$x_A\left(b\right)$

$\phantom{}≔\sum _{j\in A}{b}_j,$

$x_B\left(b\right)$

$\phantom{}≔\sum _{j\in B}{b}_j,$

$x_C\left(b\right)$

$\phantom{}≔\sum _{j\in C}{b}_j.$

Conditionally on $B_1=b$, we know that since the $X_{1j}$ are independent $𝒩(0,1)$, $(U_{\theta },V_{\theta })$ is centered and jointly Gaussian. A direct computation (Appendix A.2.2) yields its variances and covariance:

	$a_p(\theta ,b)$	$\phantom{}≔\mathrm{Var}(U_{\theta }\mid B_1=b)={\theta }^2\left(x_A\left(b\right)+x_B\left(b\right)\right),$		(33)
	$b_p(\theta ,b)$	$\phantom{}≔\mathrm{Var}(V_{\theta }\mid B_1=b)$
		$\phantom{}=4{\psi }^{2}s+\left({\left(1+\gamma \left(\theta \right)\right)}^2-4\psi \left(1+\gamma \left(\theta \right)\right)\right)x_A\left(b\right)+{\left(1-\gamma \left(\theta \right)\right)}^2{x}_B\left(b\right)$
		$+4\left(1-2\psi \right)x_C\left(b\right),$		(34)
	$c_p(\theta ,b)$	$\phantom{}≔\mathrm{Cov}(U_{\theta },V_{\theta }\mid B_1=b)$
		$\phantom{}=\theta \left[\left(1+\gamma \left(\theta \right)-2\psi \right)x_A\left(b\right)-\left(1-\gamma \left(\theta \right)\right)x_B\left(b\right)\right].$		(35)

Put

$D_p(\theta ,b)≔{\left(1-c_p(\theta ,b)\right)}^2-a_p(\theta ,b)b_p(\theta ,b).$

(36)

Whenever $D_p(\theta ,b)>0$, Lemma 5.1 gives

$𝔼[e^{-\theta {\Delta }_1}\mid B_1=b]=D_p{(\theta ,b)}^{-1/2}.$

(37)

5.2 A regularized Chernoff parameter

For $\lambda \in (0,1)$, define

${\theta }_{p,\lambda }\left(\eta \right)≔\frac{\lambda C^{\star }\left(\eta \right)}{2\alpha \psi p}=\frac{\lambda }{2\alpha \left(1-\psi \right)\left(2-\eta \left(1-\psi \right)\right)}\cdot \frac{1}{p}.$

(38)

The shrinkage factor $\lambda <1$ keeps the Gaussian product MGF uniformly inside its domain of finiteness.

Lemma 5.2.

Fix $\alpha ,\delta \in (0,1)$ and $\lambda \in (0,1)$. There exist ${\psi }_0>0$, $p_0\in \mathbb{N}$, and $\kappa >0$ such that, for every $\psi \in (0,{\psi }_0)$, every $p\ge p_0$, every $\eta \in \left[\delta ,1\right]$, and every mask $b\in {\left\{0,1\right\}}^p$,

$D_p({\theta }_{p,\lambda }\left(\eta \right),b)\ge \kappa .$

Consequently,

$𝔼[e^{-{\theta }_{p,\lambda }\left(\eta \right){\Delta }_1}\mid B_1=b]\le {\kappa }^{-1/2}$

for all such $b$.

Write

$u≔\frac{x_A\left(b\right)}{p},v≔\frac{x_B\left(b\right)}{p},w≔\frac{x_C\left(b\right)}{p}.$

Recall that $\left|A\right|=\left|B\right|=\eta s$ and $\left|C\right|=\left(1-\eta \right)s$. Then $0\le u,v\le \eta \alpha$ and $0\le w\le \left(1-\eta \right)\alpha$. Let

$k_{\lambda ,\eta ,\psi }≔\frac{\lambda }{2\alpha \left(1-\psi \right)\left(2-\eta \left(1-\psi \right)\right)},\text{so that}{\theta }_{p,\lambda }\left(\eta \right)=k_{\lambda ,\eta ,\psi }/p.$

By (32) and (38), we have $\gamma \left({\theta }_{p,\lambda }\left(\eta \right)\right)=O\left(p^{-1}\right)$. Hence, uniformly over $\eta \in \left[\delta ,1\right]$, $\psi$ in $[0,1)$, and all masks $b$, the expression $D_p({\theta }_{p,\lambda }\left(\eta \right),b)$ differs by $o\left(1\right)$ from

	$D_{\psi }(u,v,w,\eta )$	$\phantom{}≔{\left(1-k_{\lambda ,\eta ,\psi }\left[\left(1-2\psi \right)u-v\right]\right)}^2$
		$-k_{\lambda ,\eta ,\psi }^2\left(u+v\right)\left[4{\psi }^2\alpha +\left(1-4\psi \right)u+v+4\left(1-2\psi \right)w\right].$

We first lower-bound the limiting expression at $\psi =0$. We have

$k_{\lambda ,\eta ,0}=\frac{\lambda }{2\alpha \left(2-\eta \right)}.$

For $\psi =0$,

	$D_0(u,v,w,\eta )$	$\phantom{}={\left(1-k_{\lambda ,\eta ,0}\left(u-v\right)\right)}^2-k_{\lambda ,\eta ,0}^2\left(u+v\right)\left(u+v+4w\right)$
		$\phantom{}=1-2k_{\lambda ,\eta ,0}\left(u-v\right)-4k_{\lambda ,\eta ,0}^2\left[uv+w\left(u+v\right)\right].$

The right-hand side is decreasing in $w$, so its minimum over the allowed interval for $w$ is attained at $w=\left(1-\eta \right)\alpha$. With this value of $w$, the derivative in $v$ equals

$2k_{\lambda ,\eta ,0}-4k_{\lambda ,\eta ,0}^2\left[u+\left(1-\eta \right)\alpha \right]=2k_{\lambda ,\eta ,0}\left[1-2k_{\lambda ,\eta ,0}\left[u+\left(1-\eta \right)\alpha \right]\right]\ge 0,$

because $u+\left(1-\eta \right)\alpha \le \alpha$ (recall that $u\le \eta \alpha$) and $2k_{\lambda ,\eta ,0}\alpha =\lambda /\left(2-\eta \right)<1$. Hence the minimum is attained at $v=0$. The resulting expression,

$D_0(u,0,\left(1-\eta \right)\alpha ,\eta )=1-2k_{\lambda ,\eta ,0}u-4k_{\lambda ,\eta ,0}^2\left(1-\eta \right)\alpha u,$

is decreasing in $u$, and hence the minimum is attained at $u=\eta \alpha$. Therefore

	$D_0(u,v,w,\eta )$	$\phantom{}\ge 1-\eta \alpha \left(2k_{\lambda ,\eta ,0}+4k_{\lambda ,\eta ,0}^2\left(1-\eta \right)\alpha \right)$
		$\phantom{}=1-\frac{2\lambda \eta \alpha }{2\alpha \left(2-\eta \right)}-\frac{4\eta \alpha \left(1-\eta \right)\alpha {\lambda }^2}{4{\alpha }^2{\left(2-\eta \right)}^2}$
		$\phantom{}=1-\lambda \frac{\eta }{2-\eta }-{\lambda }^2\frac{\eta \left(1-\eta \right)}{{\left(2-\eta \right)}^2}$
		$\phantom{}\ge 1-\lambda ,$

where the last inequality holds because $\lambda \le 1$ and

$\frac{\eta }{2-\eta }+\frac{\eta \left(1-\eta \right)}{{\left(2-\eta \right)}^2}\le 1,\forall \eta \in \left[0,1\right].$

By continuity of $D_{\psi }$ in $\psi \in [0,1)$, uniformly over the same compact domain, there exists ${\psi }_0>0$ such that

$D_{\psi }(u,v,w,\eta )\ge \frac{1-\lambda }{2}$

for all $\psi \in (0,{\psi }_0)$. The uniform $o\left(1\right)$ approximation between $D_p$ and $D_{\psi }$ then gives the claim, after setting $\kappa ≔\left(1-\lambda \right)/4$, and $p_0$ large enough (recall that $D_p({\theta }_{p,\lambda }\left(\eta \right),b)$ and $D_{\psi }(u,v,w,\eta )$ differ by $o\left(1\right)$). ∎

Lemma 5.3.

Fix $\alpha ,\delta \in (0,1)$ and $\lambda \in (0,1)$, and take $\psi >0$ small enough for Lemma 5.2 to hold. Then we have, uniformly over $\eta \in \left[\delta ,1\right]$,

$𝔼\left[e^{-{\theta }_{p,\lambda }\left(\eta \right){\Delta }_1}\right]={(1+(2\lambda -{\lambda }^2)\eta \psi C^{\star }\left(\eta \right))}^{-1/2}+o\left(1\right).$

(39)

$U_p≔\frac{x_A\left(B_1\right)}{p},V_p≔\frac{x_B\left(B_1\right)}{p},W_p≔\frac{x_C\left(B_1\right)}{p}.$

Since $\left|A\right|=\left|B\right|=\eta \alpha p$ and $\left|C\right|=\left(1-\eta \right)\alpha p$, the three variables are sums of i.i.d. Bernoulli$\left(\psi \right)$ terms divided by $p$. For every $\rho >0$, Hoeffding’s inequality applied to $S_A:={\sum }_{j\in A}{B}_{1j}$ gives

	$\mathbb{P}\left(\left|U_p-\eta \alpha \psi \right|>\rho \right)$	$\phantom{}=\mathbb{P}\left(\left|S_A-\eta \alpha p\psi \right|>\rho p\right)$
		$\phantom{}\le 2\exp \left(-\frac{2{\rho }^2{p}^2}{\left|A\right|}\right)$
		$\phantom{}=2\exp \left(-\frac{2{\rho }^{2}p}{\eta \alpha }\right)$
		$\phantom{}\le 2\exp \left(-\frac{2{\rho }^{2}p}{\alpha }\right),$

where the last inequality uses $\eta \le 1$. The same bound holds for $V_p$. For $W_p$, the analogous computation with $\left|C\right|=\left(1-\eta \right)\alpha p$ gives, for $\eta \in [\delta ,1)$,

$\mathbb{P}\left(\left|W_p-\left(1-\eta \right)\alpha \psi \right|>\rho \right)\le 2\exp \left(-\frac{2p{\rho }^2}{\left(1-\eta \right)\alpha }\right)\le 2\exp \left(-\frac{2p{\rho }^2}{\left(1-\delta \right)\alpha }\right);$

for $\eta =1$, $W_p\equiv 0=\left(1-\eta \right)\alpha \psi$ and the probability vanishes. Each right-hand side is independent of $\eta$ and tends to zero as $p\to \infty$, so

$\underset{\eta \in \left[\delta ,1\right]}{sup}\mathbb{P}\left(\left|U_p-\eta \alpha \psi \right|>\rho \right)\to 0,$

and analogously for $V_p,W_p$. Hence

$(U_p,V_p,W_p)⟶(\eta \alpha \psi ,\eta \alpha \psi ,\left(1-\eta \right)\alpha \psi )$

in probability, uniformly in $\eta \in \left[\delta ,1\right]$.

$F_p(u,v,w;\eta )≔D_p{({\theta }_{p,\lambda }\left(\eta \right),b)}^{-1/2},$

where $u=x_A\left(b\right)/p$, $v=x_B\left(b\right)/p$, and $w=x_C\left(b\right)/p$. By Lemma 5.2, $0\le F{}_p\le \kappa {}^{-1/2}$ for all masks and all $\eta \in \left[\delta ,1\right]$. Define the compact set

$K≔\{(u,v,w,\eta ):0\le u,v\le \eta \alpha ,\mathrm{\hspace{0.33em}0}\le w\le (1-\eta )\alpha ,\eta \in [\delta ,1]\}.$

On $K$, the polynomial formula (36) together with ${\theta }_{p,\lambda }\left(\eta \right)=O\left(p^{-1}\right)$ and $\gamma \left({\theta }_{p,\lambda }\right)=O\left(p^{-1}\right)$ (uniformly in $\eta$) gives $D_p\to D_{\infty }$ uniformly, where $D_{\infty }(u,v,w,\eta )$ is the polynomial obtained by setting $\gamma =0$ in (36). Combined with the uniform lower bound $D_p\ge \kappa >0$ and the Lipschitz continuity of $x\mapsto x{}^{-1/2}$ on $[\kappa ,\infty )$, this yields

$\underset{(u,v,w,\eta )\in K}{sup}\left|F_p(u,v,w,\eta )-F_{\infty }(u,v,w,\eta )\right|⟶0,$

where $F{}_{\infty }≔D{}_{\infty }{}^{-1/2}$. Combining this uniform convergence with the concentration $(U_p,V_p,W_p)\to (\eta \alpha \psi ,\eta \alpha \psi ,\left(1-\eta \right)\alpha \psi )$ in probability (uniformly in $\eta$) and the uniform continuity of $F_{\infty }$ on $K$, we obtain

$F_p(U_p,V_p,W_p,\eta )⟶F_{\infty }(\eta \alpha \psi ,\eta \alpha \psi ,\left(1-\eta \right)\alpha \psi ,\eta )$

in probability, uniformly in $\eta \in \left[\delta ,1\right]$. Since $F{}_p\le \kappa {}^{-1/2}$, bounded convergence yields

$\underset{\eta \in \left[\delta ,1\right]}{sup}|{𝔼}_B\left[D_p{({\theta }_{p,\lambda }\left(\eta \right),B_1)}^{-1/2}\right]-F_{\infty }(\eta \alpha \psi ,\eta \alpha \psi ,(1-\eta )\alpha \psi ;\eta )|⟶0.$

Substituting

$u=v=\eta \alpha \psi ,w=\left(1-\eta \right)\alpha \psi ,{\theta }_{p,\lambda }\left(\eta \right)=\frac{\lambda C^{\star }\left(\eta \right)}{2\alpha \psi p},$

into (33), (34) and (35); and using $\gamma \left({\theta }_{p,\lambda }\right)=o\left(1\right)$, we obtain

	$c_p$	$\phantom{}⟶-\lambda \eta \psi C^{\star }\left(\eta \right),$
	$a_p{b}_p$	$\phantom{}⟶{\lambda }^2\eta \psi C^{\star }\left(\eta \right)\left(1+\eta \psi C^{\star }\left(\eta \right)\right),$

which yields:

${\left(1-c_p\right)}^2-a_p{b}_p$

$\phantom{}⟶1+\left(2\lambda -{\lambda }^2\right)\eta \psi C^{\star }\left(\eta \right).$

We spell out the cancellation in detail. Let

$T_{\eta }≔\left(1-\psi \right)\left(2-\eta \left(1-\psi \right)\right),\text{so that}{C}^{\star }\left(\eta \right)=\psi /T_{\eta }.$

At the mean mask profile,

	$c_p$	$\phantom{}⟶-2k_{\lambda ,\eta ,\psi }\eta \alpha {\psi }^2=-\lambda \eta \psi C^{\star }\left(\eta \right),$
	$a_p{b}_p$	$\phantom{}⟶4k_{\lambda ,\eta ,\psi }^2\eta {\alpha }^2{\psi }^2\left[2-\eta -2\psi \left(1-\eta \right)\right].$

Thus

	$\underset{p\to \infty }{lim}{D}_p$	$\phantom{}={\left(1+\lambda \eta \psi C^{\star }\left(\eta \right)\right)}^2-4k_{\lambda ,\eta ,\psi }^2\eta {\alpha }^2{\psi }^2\left[2-\eta -2\psi \left(1-\eta \right)\right]$
		$\phantom{}=1+2\lambda \eta \psi C^{\star }\left(\eta \right)+{\lambda }^2{\eta }^2{\psi }^2{C}^{\star }{\left(\eta \right)}^2$
		$-{\lambda }^2\eta C^{\star }{\left(\eta \right)}^2\left[2-\eta -2\psi \left(1-\eta \right)\right]$
		$\phantom{}=1+2\lambda \eta \psi C^{\star }\left(\eta \right)+{\lambda }^2\eta C^{\star }{\left(\eta \right)}^2\left[\eta {\psi }^2-2+\eta +2\psi \left(1-\eta \right)\right].$

The term in brackets equals $-T_{\eta }$, and since $C^{\star }\left(\eta \right)=\psi /T_{\eta }$, this becomes

$1+2\lambda \eta \psi C^{\star }\left(\eta \right)-{\lambda }^2\eta \psi C^{\star }\left(\eta \right)=1+\left(2\lambda -{\lambda }^2\right)\eta \psi C^{\star }\left(\eta \right).$

Combining this with (37) completes the proof of (39). ∎

Fix $S\in 𝒮$ with $M\left(S\right)\ge \delta s$, and let $\eta =M\left(S\right)/s$. Apply Chernoff’s bound (30) with $\theta ={\theta }_{p,\lambda }\left(\eta \right)$. Lemma 5.3 gives, uniformly in $S$,

$𝔼\left[e^{-{\theta }_{p,\lambda }\left(\eta \right){\Delta }_1}\right]={(1+(2\lambda -{\lambda }^2)\eta \psi C^{\star }\left(\eta \right))}^{-1/2}+o\left(1\right).$

The limiting quantity is a constant in $(0,1)$ for any $\eta \in \left[\delta ,1\right]$, raising to the $n$-th power yields

$\mathbb{P}({\Delta }_S\le 0)\le {(1+(2\lambda -{\lambda }^2)\eta \psi C^{\star }\left(\eta \right))}^{-n/2}{e}^{o\left(n\right)},$

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 ${\beta }^{\star }\in {\{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 $ds=\omega \left(p\right)$, 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 ($ds/p\to +\infty$) 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 ${\beta }^{\star }$ aligning with non-zeros of a row of $X$: $ds/p=\omega \left(1\right)$, $ds/p\to \tau$ for some $\tau >0$, and $ds/p=o\left(1\right)$. 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{\beta }^{\star }$ 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 $ds/p=\omega \left(1\right)$, while it increases dramatically in the regime where $ds/p=o\left(1\right)$.

  • –

    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\ge \left(1+\epsilon \right)n_{\text{ALG}}$, 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 $\text{P}\ne \text{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=\alpha p$ and $d=\psi p$, with $\psi >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 $\psi$, 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\left(p\right)$. 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 ${\ell }_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

$N_p≔\frac{1}{\sqrt{2\delta ds/p}}\left(\sum _{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}-2\delta ds/p\right).$

Its characteristic function writes:

		${\Phi }_{N_p}\left(t\right)$
		$\phantom{}=𝔼\left[e^{it{N}_p}\right]$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}{\left(𝔼\left[\exp \left(it{B}_{ij}/\sqrt{2\delta ds/p}\right)\right]\right)}^{2\delta s}$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}{\left(1-d/p+d/p\exp \left(it/\sqrt{2\delta ds/p}\right)\right)}^{2\delta s}$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}{\left(1+d/p\left(\exp \left(it/\sqrt{2\delta ds/p}\right)-1\right)\right)}^{2\delta s}$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}{\left(1+d/p\left(\frac{it}{\sqrt{2\delta ds/p}}-\frac{t^2}{4\delta ds/p}+𝒪\left(\frac{-i{t}^3}{{\left(2\delta ds/p\right)}^{3/2}}\right)\right)\right)}^{2\delta s}$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}{\left(1+d/p\left(\frac{it}{\sqrt{2\delta ds/p}}-\frac{t^2}{4\delta ds/p}+𝒪\left(\frac{1}{{\left(2\delta ds/p\right)}^{3/2}}\right)\right)\right)}^{2\delta s}$
		$\phantom{}=\exp \left(-it\sqrt{2\delta ds/p}+2\delta s\log \left(1+d/p\left(\frac{it}{\sqrt{2\delta ds/p}}-\frac{t^2}{4\delta ds/p}+𝒪\left(\frac{1}{{\left(2\delta ds/p\right)}^{3/2}}\right)\right)\right)\right)$
		$\phantom{}=e^{-it\sqrt{2\delta ds/p}}\exp \left(2\delta s\left(d/p\left(\frac{it}{\sqrt{2\delta ds/p}}-\frac{t^2}{4\delta ds/p}+𝒪\left(\frac{1}{{\left(2\delta ds/p\right)}^{3/2}}\right)\right)+𝒪\left(\frac{d}{sp}\right)\right)\right)$
		$\phantom{}=\exp \left(-it\sqrt{2\delta ds/p}+it\sqrt{2\delta ds/p}-t^2/2+𝒪\left(\frac{1}{\sqrt{2\delta ds/p}}\right)+𝒪\left(\frac{2\delta d}{p}\right)\right)$
		$=\exp (-t^2/2+o\left(1\right))\stackrel{p\to +\infty }{⟶}\exp (-t^2/2)={\Phi }_{𝒩(0,1)}\left(t\right),$

for all $t\in ℝ$. The result follows. ∎

A.1.2 Proof of Lemma 4.2

Write ${\Sigma }_p≔{\sum }_{j\in U_{\left[\delta s\right]}\cup V_{\left[\delta s\right]}}{B}_{ij}\sim \text{Bin}(2\delta s,d/p)$, with mean ${\mu }_p≔𝔼\left[{\Sigma }_p\right]=2\delta ds/p$. We recall:

$N_p=\frac{{\Sigma }_p-{\mu }_p}{\sqrt{{\mu }_p}},V_p=\frac{2\sigma }{\sqrt{2\delta +\frac{4{\sigma }^2}{ds/p}+\sqrt{\frac{2\delta }{ds/p}}{N}_p}},$

and note the deterministic bound $0\le V_p\le \sqrt{ds/p}$, which holds because ${\Sigma }_p\ge 0$. Fix $T>2$. Splitting on ${ℰ}_p≔\{N_p\ge -{(ds/p)}^{1/4}\}$, we have:

$𝔼\left[V_p\mathrm{\hspace{0.17em}1}\{V_p>T\}\right]={\Xi }_1+{\Xi }_2,{\Xi }_1≔𝔼\left[V_p\mathrm{\hspace{0.17em}1}\{V_p>T\}{\mathrm{\hspace{0.17em}1}}_{{ℰ}_p}\right],{\Xi }_2≔𝔼\left[V_p\mathrm{\hspace{0.17em}1}\{V_p>T\}{\mathrm{\hspace{0.17em}1}}_{{ℰ}_p^c}\right].$

Bounding ${\Xi }_1$. On ${ℰ}_p$ the denominator defining $V_p$ satisfies

$2\delta +\frac{4{\sigma }^2}{ds/p}+\sqrt{\frac{2\delta }{ds/p}}{N}_p\ge \mathrm{\hspace{0.33em}2}\delta +\frac{4{\sigma }^2}{ds/p}-\sqrt{2\delta }{\left(\frac{ds}{p}\right)}^{-1/4}.$

The right-hand side is deterministic and converges to $2\delta$, so there is $p_1\in \mathbb{N}$ with right-hand side $\phantom{}\ge \delta$ for all $p\ge p_1$. Hence $V_p\le 2\sigma /\sqrt{\delta }$ on ${ℰ}_p$ for $p\ge p_1$, so $\mathrm{𝟙}\{V_p>T\}{\mathrm{𝟙}}_{{ℰ}_p}\le \mathrm{𝟙}\{2\sigma /\sqrt{\delta }>T\}$ and

${\Xi }_1\le \frac{2\sigma }{\sqrt{\delta }}\mathrm{\hspace{0.17em}1}\{2\sigma /\sqrt{\delta }>T\},p\ge p_1.$

Bounding ${\Xi }_2$. By $V_p\le \sqrt{ds/p}$ we have $\mathrm{𝟙}\{V_p>T\}\le \mathrm{𝟙}\{ds/p>T^2\}$, and therefore:

${\Xi }_2\le \sqrt{ds/p}\mathrm{\hspace{0.17em}1}\{ds/p>T^2\}\mathbb{P}\left({ℰ}_p^c\right).$

The complementary event is a Binomial lower-tail deviation: ${ℰ}_p^c=\{{\Sigma }_p<(1-{\epsilon }_p){\mu }_p\}$ with ${\epsilon }_p≔{(ds/p)}^{-1/4}/\sqrt{2\delta }\in (0,1)$ for $p$ large. The multiplicative Chernoff bound $\mathbb{P}({\Sigma }_p\le (1-\epsilon ){\mu }_p)\le e^{-\epsilon {}^2\mu {}_p/2}$ gives

$\mathbb{P}\left({ℰ}_p^c\right)\le \exp \left(-\frac{{\epsilon }_p^2{\mu }_p}{2}\right)=\exp \left(-\frac{\sqrt{ds/p}}{2}\right),{\epsilon }_p^2{\mu }_p=\frac{1}{2\delta \sqrt{ds/p}}\cdot 2\delta \frac{ds}{p}=\sqrt{ds/p}.$

Hence, for $p\ge p_2$ (large enough that ${\epsilon }_p\in (0,1)$), we have:

${\Xi }_2\le \sqrt{ds/p}{e}^{-\sqrt{ds/p}/2}\mathrm{\hspace{0.17em}1}\{ds/p>T^2\}.$

On $\{ds/p>T^2\}$ we have $\sqrt{ds/p}>T>2$, and $x\mapsto \sqrt{x}e{}^{-\sqrt{x}/2}$ is decreasing for $\sqrt{x}>2$, so $\Xi {}_2\le Te{}^{-T/2}$.

We conclude that, for all $p\ge p^{\prime }≔\max (p_1,p_2)$, we have:

$𝔼\left[V_p\mathrm{\hspace{0.17em}1}\{V_p>T\}\right]\le \frac{2\sigma }{\sqrt{\delta }}\mathrm{\hspace{0.17em}1}\{2\sigma /\sqrt{\delta }>T\}+T{e}^{-T/2}.$

The right-hand side is independent of $p$ and tends to $0$ as $T\to +\infty$ (the first term vanishes once $T>2\sigma /\sqrt{\delta }$). Therefore

$\underset{T\to +\infty }{lim}\underset{p\ge p^{\prime }}{sup}𝔼\left[V_p\mathrm{\hspace{0.17em}1}\{V_p>T\}\right]=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 $X_j\equiv X_{1j}$, $B_j\equiv B_{1j}$, $Z\equiv Z_1$. Since ${\mathrm{𝟙}}_{S^{\star }}={\mathrm{𝟙}}_A+{\mathrm{𝟙}}_C$, ${\mathrm{𝟙}}_S={\mathrm{𝟙}}_B+{\mathrm{𝟙}}_C$, and ${\tilde{X}}_{1j}=B_j{X}_j$, set

$W≔\sum _{j\in A}{B}_j{X}_j-\sum _{j\in B}{B}_j{X}_j=⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}-{\mathrm{𝟙}}_S⟩,$

$R≔\sum _{j\in A}{B}_j{X}_j+\sum _{j\in B}{B}_j{X}_j+2\sum _{j\in C}{B}_j{X}_j=⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}⟩+⟨{\tilde{X}}_1,{\mathrm{𝟙}}_S⟩,$

and

$D≔\sum _{j\in S^{\star }}{X}_j=⟨X_1,{\mathrm{𝟙}}_{S^{\star }}⟩.$

Expanding ${\Delta }_1$. Factoring the difference of squares in the definition of ${\Delta }_1$ and using $⟨{\tilde{X}}_1,{\mathrm{𝟙}}_S⟩-⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}⟩=-W$, we get:

${⟨{\tilde{X}}_1,{\mathrm{𝟙}}_S⟩}^2-{⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}⟩}^2=\left(⟨{\tilde{X}}_1,{\mathrm{𝟙}}_S⟩-⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}⟩\right)\left(⟨{\tilde{X}}_1,{\mathrm{𝟙}}_S⟩+⟨{\tilde{X}}_1,{\mathrm{𝟙}}_{S^{\star }}⟩\right)=-WR,$

while the cross term equals $2\psi \left(D+Z\right)W$. Hence

${\Delta }_1=-WR+2\psi \left(D+Z\right)W=W\left(2\psi D-R\right)+2\psi WZ,$

and therefore:

$-\theta {\Delta }_1=\theta W\left(R-2\psi D\right)-2\theta \psi WZ.$

Integrating out $Z$. Only the final term involves $Z$. Conditioning on $(X_1,B_1)$ and integrating $Z\sim 𝒩(0,{\sigma }^2)$,

$𝔼[e^{-2\theta \psi WZ}\mid X_1,B_1]=e^{\frac{1}{2}{\left(2\theta \psi W\right)}^2{\sigma }^2}=e^{2{\theta }^2{\psi }^2{\sigma }^2{W}^2}=e^{\theta \gamma \left(\theta \right)W^2},$

where the last equality holds by $\gamma \left(\theta \right)=2{\psi }^2{\sigma }^2\theta$ from (32). Therefore

	$𝔼\left[e^{-\theta {\Delta }_1}\mid B_1\right]$	$\phantom{}={𝔼}_{X_1}\left[\exp \left(\theta W\left(R-2\psi D\right)+\theta \gamma \left(\theta \right)W^2\right)\mid B_1\right]$
		$\phantom{}={𝔼}_{X_1}\left[\exp \left(\theta W\left(R-2\psi D+\gamma \left(\theta \right)W\right)\right)\mid B_1\right].$

With $U_{\theta }≔\theta W$ and $V_{\theta }≔R-2\psi D+\gamma \left(\theta \right)W$, the exponent is $U_{\theta }{V}_{\theta }$, which is (31).

Explicit form of $U_{\theta },V_{\theta }$. Now we have:

$U_{\theta }=\theta W=\theta \left(\sum _{j\in A}{B}_j{X}_j-\sum _{j\in B}{B}_j{X}_j\right).$

Regrouping $V_{\theta }$ by index set, we obtain:

	$V_{\theta }$	$\phantom{}=\left(\sum _{j\in A}{B}_j{X}_j+\sum _{j\in B}{B}_j{X}_j+2\sum _{j\in C}{B}_j{X}_j\right)-2\psi \left(\sum _{j\in A}{X}_j+\sum _{j\in C}{X}_j\right)$
		$+\gamma \left(\theta \right)\left(\sum _{j\in A}{B}_j{X}_j-\sum _{j\in B}{B}_j{X}_j\right)$
		$\phantom{}=\sum _{j\in A}\left(\left(1+\gamma \left(\theta \right)\right)B_j-2\psi \right)X_j+\sum _{j\in B}\left(1-\gamma \left(\theta \right)\right)B_j{X}_j+2\sum _{j\in C}\left(B_j-\psi \right)X_j,$

matching the definitions in Section 5. Since $U_{\theta }$ and $V_{\theta }$ are linear in the Gaussian vector $X_1$ with coefficients determined by $B_1$, the pair $(U_{\theta },V_{\theta })$ is, conditionally on $B_1$, centered and jointly Gaussian. ∎

A.2.2 Conditional variances and covariance of the Gaussian pair

Fix a mask realization $B_1=b$ and abbreviate $X_j\equiv X_{1j}$, $\gamma \equiv \gamma \left(\theta \right)$. Conditionally on $B_1=b$, the $X_j$ are independent $𝒩(0,1)$, so $U_{\theta }$ and $V_{\theta }$, being linear in ${\left(X_j\right)}_{j\in \left[p\right]}$, are centered and jointly Gaussian, and their conditional second moments are obtained by summing products of their $X_j$-coefficients over $j$, the sets $A,B,C$ being disjoint. Throughout we use $b_j\in \left\{0,1\right\}$, hence $b_j^2=b_j$, together with $\left|A\right|+\left|C\right|=\left|S^{\star }\right|=s$. Reading off the definitions of $U_{\theta }$ and $V_{\theta }$ in Section 5, the $X_j$-coefficients of $U_{\theta }$ are $\theta b_j$ on $A$, $-\theta b_j$ on $B$, and $0$ on $C$; those of $V_{\theta }$ are $\left(1+\gamma \right)b_j-2\psi$ on $A$, $\left(1-\gamma \right)b_j$ on $B$, and $2\left(b_j-\psi \right)$ on $C$.

Variance of $U_{\theta }$. Summing the squared coefficients, we obtain:

$\mathrm{Var}(U_{\theta }\mid B_1=b)={\theta }^2\sum _{j\in A}{b}_j^2+{\theta }^2\sum _{j\in B}{b}_j^2={\theta }^2\left(x_A\left(b\right)+x_B\left(b\right)\right),$

which is (33).

Variance of $V_{\theta }$. The per-coordinate squared coefficients are

	$j\in A:\phantom{}$	${\left(\left(1+\gamma \right)b_j-2\psi \right)}^2=\left({\left(1+\gamma \right)}^2-4\psi \left(1+\gamma \right)\right)b_j+4{\psi }^2,$
	$j\in B:\phantom{}$	${\left(\left(1-\gamma \right)b_j\right)}^2={\left(1-\gamma \right)}^2{b}_j,$
	$j\in C:\phantom{}$	${\left(2\left(b_j-\psi \right)\right)}^2=4\left(1-2\psi \right)b_j+4{\psi }^2,$

using $b_j^2=b_j$. Summing over each set and combining the constant $4{\psi }^2$ terms through $\left|A\right|+\left|C\right|=s$, we obtain:

$\mathrm{Var}(V_{\theta }\mid B_1=b)=4{\psi }^{2}s+\left({\left(1+\gamma \right)}^2-4\psi \left(1+\gamma \right)\right)x_A\left(b\right)+{\left(1-\gamma \right)}^2{x}_B\left(b\right)+4\left(1-2\psi \right)x_C\left(b\right),$

which is (34).

Covariance. The $U_{\theta }$-coefficient vanishes on $C$, so only $A$ and $B$ contribute:

	$\mathrm{Cov}(U_{\theta },V_{\theta }\mid B_1=b)$	$\phantom{}=\sum _{j\in A}\left(\theta b_j\right)\left(\left(1+\gamma \right)b_j-2\psi \right)+\sum _{j\in B}\left(-\theta b_j\right)\left(\left(1-\gamma \right)b_j\right)$
		$\phantom{}=\theta \sum _{j\in A}\left(\left(1+\gamma \right)-2\psi \right)b_j-\theta \sum _{j\in B}\left(1-\gamma \right)b_j$
		$\phantom{}=\theta \left[\left(1+\gamma -2\psi \right)x_A\left(b\right)-\left(1-\gamma \right)x_B\left(b\right)\right],$

which is (35). ∎

A.2.3 Proof of Lemma 5.1

The covariance matrix $\Sigma =\left(\begin{array}{cc}a& c\\ c& b\end{array}\right)$ is positive semidefinite, so $det\Sigma =ab-c^2\ge 0$. We split according to whether $\Sigma$ is positive definite ($ab>c^2$) or degenerate ($ab=c^2$); the degenerate case is further divided into two sub-cases.

Case 1: $\Sigma \succ 0$. For $G={(U,V)}^{⊺}$, since $UV=\frac{1}{2}{G}^{⊺}JG$, where

$J=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),$

the standard quadratic-form Gaussian MGF formula gives

$𝔼\left[e^{UV}\right]=det{(I-\Sigma J)}^{-1/2}$

provided ${\Sigma }^{-1}-J\succ 0$; otherwise the integral diverges. Since $det\left({\Sigma }^{-1}-J\right)=det\left({\Sigma }^{-1}\right)det\left(I-\Sigma J\right)=\left({\left(1-c\right)}^2-ab\right)/det\left(\Sigma \right)$ and $det\left(\Sigma \right)=ab-c^2>0$ by positive definiteness, the condition ${\Sigma }^{-1}-J\succ 0$ is equivalent to $D={\left(1-c\right)}^2-ab>0$. Computing

$I-\Sigma J=\left(\begin{array}{cc}1-c& -a\\ -b& 1-c\end{array}\right),$

we obtain $det\left(I-\Sigma J\right)={\left(1-c\right)}^2-ab=D$, proving the claim.

Case 2: $\Sigma$ is degenerate with $a=0$ or $b=0$. Then $c^2=ab$ forces $c=0$, so $U=0$ a.s. or $V=0$ a.s. In either case, $UV=0$ a.s. and $𝔼\left[e^{UV}\right]=1$, which agrees with $D={\left(1-c\right)}^2-ab=1$, so $D{}^{-1/2}=1$.

Case 3: $\Sigma$ is degenerate with $a,b>0$. Then $c^2=ab$, so $V=\left(c/a\right)U$ a.s. with $U\sim 𝒩(0,a)$. Hence $UV=\left(c/a\right)U^2$ where $U^2/a\sim {\chi }_1^2$, giving

$𝔼\left[e^{UV}\right]=𝔼\left[e^{c\cdot U^2/a}\right]={(1-2c)}^{-1/2}\text{if }c<1/2,$

and $+\infty$ otherwise. On the other hand,

$D={\left(1-c\right)}^2-ab={\left(1-c\right)}^2-c^2=1-2c,$

so the formula $𝔼\left[e^{UV}\right]=D^{-1/2}$ holds, and the $D>0$ condition matches. ∎