The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Authors: Youssef Chaabouni
David Gamarnik
Venue: NeurIPS 2025 poster ()
Keywords: Sparse linear regression
Data sparsification
Sparse support recovery
Sparse data
Compressed sensing
High-dimensional statistics
Information-theoretic limits
Primary area: theory
TL;DR: We study high-dimensional sparse linear regression: discover the exact sampling complexity when the data is intrinsically sparse, and establish a sufficient condition on sample size when sparsifying originally dense data.

Abstract: We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery using a sparse design exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$ for the number of measurements, 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. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non‑zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade‑off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = \alpha p$ and $d = \psi p$ with $\alpha, \psi \in \left(0,1\right)$ and $\psi$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = \Theta\left(p / \psi^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress.

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni
David Gamarnik
Operations Research Center Massachusetts Institute of Technology Cambridge, MA 02139, USA youss4040mi t. edu
Operations Research Center Massachusetts Institute of Technology Cambridge, MA 02139, USA gamarnikemi edu
Abstract
We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the high-SNR regime where ds - +000, sparse recovery using a sparse design exhibits a phase transition at an SP
information-theoretiic threshold of πiNF θ (s log (p/s) / log (ds/p)) for the number measurements, 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. This expression makes the price of sparsity explicit: restricting each measurement d non-zeros inflates the required sample size by a factor of log s/ log ()) revealing precise trade-off between sampling complexity and measurement sparsity. Additionally, sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of ap and d tpp with a. v/ E (0, 1) and 1 small that (p/*?) is sufficient for recovery, subject certain
examine the effect of
sample of size NINF uniform integrability conjecture, the proof of which is work in progress.
Sp-ified
Introduction
In recent years, sparse signal recovery has gained significant attention, motivated by applications in
compressive sensing 7 [ 5); signal denoising [3] sparse regression [33; data stream computing
4 [4] combinatorial group testing [6]; etc. Practical examples range from the single-pixed camera, MRI scanners and radar remote-sensing systems to error-correction schemes in digital communications and widely used image-compression formats 7 Chap.
The problem can be formulated as follows. Consider a signal 3* TRP, unknown but priori s-sparse for some given S p, random measurement matrix X Rexp (also referred to design. features or data) and a noise vector Z ~ A (0, I²),), where n E N denotes the sample size and o² > 0 fixed constant. An vector of observations (also known labels annotations) is given by:
XB + Z.
Sparse recovery refers to reconstructing 3* given and Y. Intuitively, this problem can be reduced to recovering the support S* of f²*, i.e. the set of indices of its non-zero components. In fact, once the support 5* identified, the full signal can be estimated using the corresponding columns of X via the closed-form muximum-likeeibann estimator formula ÍLE X Y. where X denotes the Penro-e pseudoinverse of the submatrix formed by the columns of with indices in S* [I0]
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Traditionally, X is considered to be dense random matrix with sub- Sab--aassiin entries. Previous works have shown that the complexity of the problem in terms of required sample size exhibits two phase transitions at two thresholds TINT nALG. yielding three regimes:
n < nINE: impossibility of recovery. Reeves et al. [66 show that if n S (1 (1 TAN then the recovery of any fraction of the support of the signal is impossible.
DIN < n < RALG: super-polynomial complexity. Gamarnik and Zadik 8 show that if n 2 (1 +++) TINT then the mexiimum-ikkelhonn estimator (MLL)) recovers the support of Sr. Although solvable, the problem is widely believed to be algorithmically hard since the MLE exhibits an Overlap Gap Property (OGP) [8).
n > nALG: polynomial-tin recovery. Wainwright [18] shows that if n 2 (1+ + e) nALG then the succeeds in recovering the support of 3*.
LASSo 7
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. addition, they enable efficient signal recovery algorithms by taking advantage of the structural properties of the problem 19]. However, this sparsity comes at the cost of increased sampling complexity [99]. 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. 19 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 3 that align with non-zero components of row of X. The three regimes are: ds/p - +oc, ds/p 7 for some constant 0, and ds/p - 0. They show that in each regime, the number of samples n must exceed specific information -thooreti lower bound for any algorithm to reliably recover the signal's s support. In particular, in the first regime, where ds/p - +00, the necessary condition threshold of [19 is the same as the one of the dense case, while increases dramatically in the third case, where ds/p - 0. They work with entries rescaled so that Var (X3+* matches the dense case, while we keep Var (X,z) 1. The settings are equivalent since any scaling of X can be accounted for in S*.
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. 3 E {0, 1)". Note that in this case, recovering the support is equivalent to recovering the signal. This assumption is very common in the literature 16 g Intuitively, detecting a component of size is at least as hard as detecting stronger component, so the resulting thresholds are representative of signals with non-zery entries bounded away from zero by i.e. _* {3 E R": || and minje(p) :8 18,70 |رك] 2 1}. Our first main result (Theorem [ states that in the high signal-to-noke ratio (SNR) regime where ds/p + +00, if the number of samples n is larger than a threshold given by:
INF = - (
s log (p/s) log (ds (ds/p)
(1)
then the MLE asymptotically recovers the support of the signal. The proof uses large deviation techniques to bound the probability that a different support has a lower error than the true one, and a union bound over such supports. Bringing our result together with the necessary condition shown by Wang et al. [9) we reveal that the problem exhibits phase transition - similar to the one known in the dense case - at the Efformation-theoreet
threshold Sp In fact, if there exists a constant E > 0 such that n < (1 - E) SP then it is cearmation-theoretican impossible to ensure a reliable recovery of the support of the signal, and if there exists a constant then the MLE ensures reliable recovery of the support. Our findings therefore answer the question of exactly how much data is needed for recovery. However, we note that the recovery that we show in the sufficiency statement holds in weaker sense than the non-recovery in the necessity statement. We call the amount of additional observations in the sparsification setting compared to the dense one price of sparsity. Precisely, restricting each measurement to d non-zeros inflates the required sample
such that n 2 (1 + E) n

---

size by factor of I = θ (log s/ log (ds/p)), quantifying the sampling complexity vs. measurement sparsity trade-off.
Regarding the computational complexity, Omidiran and Wainwright [.5 show that the LASSO performs as well in the sparse setting 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:
AALG 2s log (p -8)
specifically for the LASSO to ensure reliable polynomial time recovery of 3 Although the sparsity assumption under which this result holds allows for the density rate d/p to go to 0 as p + +o0, still doesn't allow the measurements to be very sparse. In fact, it requires that:
d/p- (s-1/3 and d/p- = w ((hee log (p pp-s) 1/31
( {
(2)
log (p - s)
This raises a question about what happens in more sparse regime. Although we don't address the algorithmic threshold, i.c. the question of polynomial-time time recovery, we discover herein a sufficient condition for recovery that allows for more sparsity, allowing for future investigation in this direction.
1.2 Sparsification
The applications of the signal recovery problem 7 Chapter considered in this paper can be broadly categorized into two classes:
Applications where X is designed, c.g. involving signal compression and reconstruction. Applications where 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?
This setting, in which the observations are generated with dense measurement matrix, but the signal recovered using sparsified version of it, closely related to the "missing covariates" or "miisingg-t-rraddor" at-random" framework studied in high-dimensional statistics. Prior work by Loh and Wainwright [12) established algorithmic eg-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 ietormation-thhrreee 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 linear sparsification regime where s = ap and d = vp for constant a, & E (0, 1). Specifically, our second main result (Theorem 3 states that if the number of samples larger than threshold given by:
2h (a)
(3)
log
1 (1 (1-6)22 (1-0)2-8(11-
then the minimizer of the mean squared error (MSE) based on sparsified measurements and accordingly- rescaled observations asymptotically recovers the true support up error fraction 8 E (0, 1). In particular, support recovery is possible for arbitrarily aggressive sparsification, i.e. arbitrarily small ub. In the strong- crrosn-pparsiiicatton regime where 1éb + the sufficient threshold (3) effectively writes:
Sp-ified INF
P
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 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. Based on our result, this has order θ (Vp/n)
when n = Ω (p).
3

---

1.3 Contributions
To the best our knowledge, this work is the first address the following:
1. Establish a necessary and sufficient condition for sparse recovery in the sparse setting,
2. Provide a sufficient condition for sparse recovery after sparsifying an originally dense design, conditional on a mild uniform-integrabiliy conjecture.
1.4 Outline and Notations
We organize the rest of the paper as follows. Dection[istudinn the sparse measurement setting. Section
3 examines recovery after sparsifying an originally dense measurement matrix. Section 4 concludes and sketches future work directions.
Throughout this document, we will use the following notations:
We denote by h (-) the binary entropy: (x) -r log x (1 x)) log x)), (0, We call fo-nrrm the number non-zero coordinates of x E Rd, that is || == Ei_ (x: + 0).
Sparse Recovery using Sparse Measurements
2.1 Setting
Let n,,,8, d E N such that d, S p. We define a sparse Gaussian matrix in Rexp as follows. Definition 2.1 (Sparse Gaussian matrix). We call X [Xxsketm])jep)] Rx* a sparse Gaussian
matrix with parameter d if for all E [n]..j E [p] we have:
Xi Bij.Naj.
where (Big) Ber (d/p) and (N:p (en) iid. N' (0,1) are mutually independent.
Remark 2.1. Note that is the expected number of non-zero components per row of X. In our setting, we think of d as being of smaller order of magnitude than In particular, d = o (p).
Let X be sparse Gaussian random matrix of parameter and Z be random vector in IR such that Z ~ V (0, I²),), with o > 0 a fixed constant. Let 3 E {0, 1}" be a deterministic vector such that ||S*| ll = s. We define the random vector as:
Y = X + Z.
(5)
Of particular interest is the signal-to-non ratio (SNR), known to be an important quantity for characterizing the difficulty of sparse recovery problems [6]. It's defined as follows:
E X 1
ds 2o
SNR
(6)
The maximum likelihood estimator (MLE) of 3t is defined by the random vector:
arg min 3 118
|Y
X
We are interested in the minimum number of samples required so that the MLE asymptotically recovers the true signal 6*. We formalize the problem as follows.
2.2 Problem
We start by defining the support of vector and the symmetric difference of supports.
Definition 2.2 (Support). Let RP. We call support of the set of indices of the non-zero components of u and denote it Supp (u) = {i [p]: u, # 0}. Note that [Supp (u)l = ||u|lo-
Definition 2.3 (Symmetric difference). We call symmetric difference between two sets S and S2 the set of elements in one but not the other and denote it S₁ A S2 = (Si U.))) (S n.S2).

---

We formalize the problem we address below as follows: given an error tolerance E (0, 1), we wish determine the minimum number of samples n. as function of p. and d required so that:
2x,2 z ( Supp (8*) A Supp ( < 28s)
+ 1, n, s, -00.
2.3 Results
Our first main result, Theorem [ provides sufficient condition on the sample size for reliable support recovery when using sparse measurements.
Theorem (Sufficient conditions for sparse recovery using sparse measurement matrices), Suppose p, 8, - +0c, d o (p) and ds- (p) (i.e. SNR +00). Let d E (0, We consider two different regimes.
1. Assume o (p). Let
2s log (p/s)
log (ds/p) + log (6/(2o²))
If there exists e >> O such that n 2 + 8) mai then the MLLE recovers 3 up to error w.h.p.:
(1 (Supp (8*) A Supp (
20s) 2 1 exp (- E=sllog (p/s) + to (slog (p/s)))
P Fx,2 as d + +00.
2. Assume there exists a constant a E (0, 1) such that
Let:
2h (ai) p
Tlin
log d + log (da/ (2o)))
where h (+) denote the entropy function. If there exists such that 2 (1 + 8) tim then the MLE 3 recovers 3 up to error ó w.h.p.:
Px Supp (8*) Supp
(8) < 28s) 2 2-eexp (a) (-e
as 8, d + +00.
The proof Theorem given in appendix A. uses large deviation techniques 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 brief proof sketch of Theorem [
Proof sketch. Let S denote the set of supports of cardinality and S = Supp (5*). For any S E S, we denote by I the vector {0, 1)2 such that [1s = (i E S) for all i [p). We define the loss function over such that T. (S) = ||Y X1sll so that Supp
arg minses (S). As 3
p gets large, the event "L (S) L (S*)" for any S such that IS A Chernoff bound yields:
S
2ds is event. The
2022
log ((()) < LS*) < log
+ +0(1)
dds
This step involves most of the technical work. Then, by union bound:
P
Supp
(8) A
< 25s} 2
Σ
P(L < <L())) 2
(p)
220²p 8ds
n/2
SISAS 286
log Hogdds/))
Solving for n, we obtain critical threshold of n²
We conclude.
Bringing together Theorem | with the necessary conditions shown by Wang al. in 19 we obtain the following corollary. ihfermaaionn-heorrttie Corollary 2 (Information- theoretie phase transition). The spurse recovery the sparse setting problem exhibits phase transition at ieformation-theoreee threshold SP
nipp.
5

---

1. In the first regime considered above, the expression of nINE is given by:
2s log (p/s)
SP
INF
log (ds/p)
In the second regime considered above, the expression of WINE is given by:
2h (a)
INF
log d
Specifically, in each of these regimes:
(i) If there exists 0 such that S (1 E) PINr then, as n, - too, there exists decoder
Rn + 1B E 10, 11 = 8 such that:
Px.z (x.((g()) # Supp (3*) - O.
max 8'E l1 11,=
this sense, it is cntoomation-thhoetticcee impossible to ensure an asymptotically reliable recovery. (ii) If there exists E > such that n 2 (1+ ninr- then as n. P, 3,
to0:
Supp
3
A Supp (8*)
0,
2s
in probability. In this sense, the MLE
7 ensures an asymptotically reliable recovery.
The proof of Corollary [ given in appendix A.2 Statement (i) is due to Wang al. 19 while statement (ii) follows from Theorem [ and is the main contribution of this section.
Remark 2.2 (Limitations). We note that the definition of "recovery" not the same statements (f) and (ii) of Corollary 2 The necessity statement (i) is about the impossibility vanishing probability of exact equality of supports, which stronger than the sufficiency statement of vanishing rescaled error in (ii). In particular, it is possible in theory that both statements hold simultaneously. To the best of our knowledge, the literature on the dense setting also suffers from this gap (see B 18).. While Reeves al. [16] establish clean information information-theoretie phase transition in the dense setting (using the same definition of "recovery" for both bounds), their analysis considers different problem settings and convergence guarantees than ours.
We interpret Theorem T and Corollary as follows.
Phase transition. For simplicity, only discuss the sublinear sparsity regime, defined by s o (p). Previous works on sparse recovery in the dense case (166) (8) have shown the existence of an
information-theoreticc threshold:
2s log (p/s)
TANNF
8
log
at which the complexity of support recovery in terms of sample size exhibits phase transition, where repport
the recovery of any fraction of the support is impossible for (1 E) TINT, and full recovery is guaranteed by the MLE for n 2 (1 + e) Pane. In light of this, we ask the support recovery problem for the class of sparse measurement matrices described above exhibits a similar behavior. In Corollary [ we show that indeed, it exhibits similar phase transition at an information threshold given by:
2s log (p/s)
SP INF
log (ds/p)
we summarize these information tnformation-theoretiic theoretic thresholds alongside known algorithmic thresholds for the sublinear sparsity regime (s o (p)). highlighting the comparison between dense and sparse measurements in the high-SNR setting.
Table I
Price Sparsity. particular, we notice that nie 2 TINF- This confirms the intuition that sparse recovery requires more samples in the sparse measurement case: in fact, due to the sparsity of the measurement matrix, there is a low probability for the coefficient of component of the signal at given observation to be non-zero, and hence the need for larger sample size for recovery. In light

---

Table 1: Comparison of Sample Complexity Thresholds for Sublinear Sparsity (s = (p)).
Info-Theoretic Necessary
Info-Theoretic
Algorithmic Necessary
Algorithmic Sufficient
Measurement
Sufficient
Dense
2s log(p/a)
2a login/s)
16
2s log(p s)
2s log(p s)
log s
log s
Sparse,
(s/s) (ug(ds/p)
Ing(p/s) log(ds/p)
(Thm)
Unknown
2s lp -
15
high SNR
Holds under the slow decay of sparsity assumption in 15
of this, Corollary 2 is be interpreted as providing an 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:
SP
log
INE
log (ds/p) 1.
VIINF
Dependence on d and s. Note that the expression of the price of sparsity heavily depends on the regimes of and The smaller the density rate d/p, the more "expensive" the desired sparsity of the measurements is, as suggested by the expression of I. In particular, I' could take any value in (1, +.)) depending the regimes of d and 8 w.r.t. p.
Example 2.1. Consider the setting where = p" d = p with a, 3 E (0, such that + 3 > 1. Then r a/ (a - 1) E (1, +oc), which goes to when goes to 1 (low measurement sparsity), and goes to +oo when is fixed and / goes to
(high measurement sparsity).
Measurement sparsity vs. Sampling complexity trade-off. In this context, we conclude the existence of measurement sparsity sampling complexity trade-off, which also be interpreted as trade-off between sampling complexity and computational cost. We consider an example that highlights this trade-off.
Example 2.2. Let wh: [e, +00) - [e, +oo) such that &i (ar) x/ log Consider two mea- surement matrices: X1 a dense Gaussian in Rm and X2 sparse Gaussian R==x with only d = min (pe(1), s (o (p)))) expected non-zero entries per row; and an s-sparse signal 3* E TRP,, in the linear sparsity regime where 8 = op for constant a E (0, 1). On one hand, the number of samples required for reliable recovery raises from n1 = ЛINe = (p/ log in the dense case to 722 = nINF (p/ log d) in the sparse one. On the other hand the computational cost recovery the support is better in the sparse case, as maatrxxvvector multiplication cost drops from rip = O ((p²/ log p) to a2d = O (pd/ log d). This highlights a tradc-off between sampling complexity and computational cost. Proofs of these statements are given in appendix A.3
Allowing for more sparsity. Note that the sparsity assumption under which Theorem guarantees reliable recovery when there exists E > 0 such that n 2 (1 + nINF. which is:
ds/p- - +00.
(10)
is weaker than the sparsity assumption of the sufficient algorithmic threshold of Omidiran and Wainwright [15] which guarantees polynomial -ittomil---meeeeeee recovery if there exists & > 0 such that n 2 (1 =) nALG- As they show, this holds under the assumption that:
log log (p s)
min
+00.
log (p -
For example, when & = + (p), this requires that d = w (p2/3), while our result holds under the weaker assumption of = w (1). Our result allows for significantly better sparsity, but this comes at the cost of potential super-polynomial computational complexity, since computing the MLE (7) is exponential-tie in general.
3
Improving Sparse Recovery via Sparsification
3.1 Setting
Let n, E N and 3 {0, 1)" s-sparse, defined in Section 2.1 Let X E Raxp such that
(X (Xts) N (0, 1) and 7 ~ N (0, with a > 0 constant. Let Y = X33 + Z E R..
7

---

iid Ber (d/p). We define the following sparsified version of X:
Let (Bu))Emn)JE
X Rxx such that X.j == BigXiy, Vi E [n].] E [p].
(11)
In addition, we define a rescaled version of Y as follows:
d - E..
Y =
(12)
P
An estimator of 3* is defined by the random vector:
x
=
arg min Be(o,1),,11e 11
(13)
That is, the observations are generated with a dense measurement matrix (X), but the signal is recovered using a sparsification of that matrix (X)) We formalize the problem we address below as follows: given enror tolerance å (0, 1), wish to determine the minimum number of samples in terms of p, s and d required so that:
Px,z
Supp (8*) A Supp ( < 25x)
- 1, as n1, 8, -00
3.2 Results
Our second main result, Theorem g provides sufficient condition the sample size for reliable support recovery after sparsifying an originally dense measurement matrix.
Theorem 3 (Sufficient conditions for sparse recovery using sparsified measurements). Suppose that
p + +o and there exist a, va E (0, 1) such that s = op and d = vpp. Let E (0, 1). Let:
2h (xx) p
Sisp ified
(14)
log
óy
6(1-
If there exists > O such that 2 (1 + mip-iteed then, under Conjecture B. error 8 w.h.p.:
B recovers 3* up to
P Supp (8*) A Supp (3) < 285) 21 1 -exp -cxp((c((0)pootn)
as nz, 8, d + +00.
Remark 3.1 (Limitations). We show that this result holds under mild iniform-integrablln conjecture. The statement of the conjecture is deferred to appendix (BeendixB((Coneeetuuue [B.I] as it requires delving into technical details of the proof. expect it to follow from standard concentration bounds as all relevant random terms are sub-Gaussian, and verification is work in progress.
The proof of Theorem 3 is given in appendix B It follows the same general outline as the proof of Theorem [ but is much more technically involved. In particular, deriving the large-deviation bound harder because the MSE no longer decomposes neatly: Y does not correspond to the true observations of the sparsified data but rather rescaling of the original observations (12). Instead of repeating a sketch here, we simply refer the reader back to the earlier proof sketch (see section 2.3 We interpret Theorem follows.
Arbitrary sparsification rate. According to Theorem 3 support recovery is possible for arbitrarily aggressive sparsification, i.e. arbitrarily small v. provided large enough sample size.
Strong-sparsification regime. In the strong- saanssssariiiittionn regime where v + 0, the denominator of nispilied in (14) is effectively 5uh2 (2 6), and hence the sufficient condition upper bound writes:
2 (2 6) h (ax)
Sp-ified "INT
θ
(15)
Price of Sparsification. We interpret our result as providing 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 crong-sparsifiicttinn regime, it writes:
Sp-ified
+ (p/v2)
llogp 6²
INF
I Sp-catioon
θ
INN
+ (p/ log
8

---

Unlike the intrinsically-sparsee observaiosssssnionn 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 (24) that in the linear sparsity regime where d = θ (p), the price of sparsity is constant (i.e. bias in the observations that we explain T=) Instead, the price of sparsification is due
by the fact that the sparsified observations Y were not obtained as noisy projections of the true signal as in the original model ( but rather via a naive 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 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 budger. According to our result (5),, its expression in the strong-sparsification regime is given by:
Vhudget = θ VPpn))
particular, the above expression only makes sense when n S2 (p), below which Theorem does not hold.
4 Conclusion and Future Work
In the first part of this paper, we have studied the problem of recovery of a binary signal 3 E {0, 1)" based 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 w (p), i.e. high-SNR regime it is possible recover the true support asymptotically when the sample size is larger than the threshold given by Theorem [] Combining our work with the necessary conditions of Wang al. [19), we reveal an information- theoretic phase transition. The expression of the phase-transition threshold makes the price of sparsity explicit, revealing precise trade-off between sampling complexity and measurement sparsity. In the following, we present quick summary of all to the best of our knowledge results on sparse recovery the sparse measurement setting, along with some future work directions.
Information thhooreticc threshold, sufficient conditions. In Theorem I establish sufficient condition for reliable recovery. However, this result is conditional on the high-SNR (ds/p + +00) assumption. This raises the question of sufficient conditions when the measurements and signal even more sparse.
pnarmattional-hhooetiii threshold, necessary conditions.
Wang al. [19] have studied this problem. Their work reveals three regimes of behavior depending on the scaling of the expected number of non-zeros of 3* aligning with non-zeros of a row of X: ds/p
(1), ds/p + T for some т >> O, and ds/p = o (1). For their model, where the variance of the non-zero components of X scales in a way that makes the second moment of the projected signal X remain the same 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 = w (1), while increases dramatically in the regime where ds/p = o (1).
In the dense setting, Reeves al. [16] have shown that even the recovery 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. would be interesting to extend this property to the sparse setting.
Algorithmic threshold, sufficient conditions. Omidiran and Wainwright [15 have shown that under a low-sparsity assumption on the measurements, the sufficient condition of the dense setting, i.e. n 2 (1 + E) fALG. is sufficient for the sparse setting as well. It would be interesting to explore the question of polynomial-tin recovery stronger sparsity regime.
Algorithmic threshold, necessary conditions. Although cannot really hope to provide necessary conditions for polynomial-tin
recovery unless conditionally on P * NP - it would be interesting provide threshold under which the problem is believed to be algorithmically hard, as done by Gamarnik and Zadik g 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 linear sparsity and linear sparsification regime where and d = up for constant a, th E (0, 1), possible recover the true support asymptotically when the sample size is larger than threshold given by Theorem 3 This reveals that support recovery is possible for arbitrarily aggressive sparsification provided a large enough sample size, and provides an upper bound on the price of sparsification.
Nevertheless, we believe that the sparsification problem is infeasible for strong enough regimes of sparsification. In particular, we conjecture that the recovery is information-thhcorticaall impossible no matter the sample size in the sub-linear sparsification regime where d (p). We leave the exploration of this regime for future work.
Acknowledgments and Disclosure of Funding
This work was supported by the National Science Foundation (NSF) under grant CISE-2233897, Youssef Chaabouni thanks Soulef Frikha for long-standing mathematical inspiration, and Mehdi Makni for many years of insightful discussions. He also thanks Marouane Nejjar, Panos Tsimpos, and Malo Lahogue for valuable feedback and exchanges.
References
[1] Shuchin Aeron, Venkatesh Saligrama, and Manqi Zhao. Information theoretic bounds for compressed sensing. IEEE Transactions Information Theory, 56(10)51111-5130 2010.
[2] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: exact
signal reconstruction from highly incomplete frequency information. IEEE Transactions information theory, 52(2):489- 2006.
[3] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159, 2001.
[4] Graham Cormode and Marios Hadjieleftheriou. Finding the frequent items in streams of data. Communications of the ACM, 52(10):97-105, 2009.
[5] David L Donoho. Compressed sensing. JEEE Transactions information theory, 52(4): 1289- 1306, 2006.
[6] Zing-Zhu Du and Frank Kwang-ming ming Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 1999.
[7] Simon Foucart, Holger Rauhut, Simon Foucart, and Holger Rauhut. An invitation to compressive sensing. Springer, 2013.
[8] David Gamarnik and Ilias Zadik. Sparse high-dimensional linear regression. estimating squared error and a phase transition. The Annals of Statistics, 50(2):880-903, 2022.
[9] Anna Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 986))937-947, 2010.
[10] Trevor Hastie. The elements of statistical learning: data mining, inference, and prediction, 2009.
[11] Piotr Indyk. Sketching, streaming and sublinear-space algorithms. Graduate course notes, available at, 33:617, 2007.
[12] Po-Ling Loh and Martin Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in neural information processing systems, 24, 2.
[13] Alan Miller. Subset selection in regression. chapman and hall/CRC, 2002.
[14] Shanmugavelayutham Muthukrishnan et Data streams: algorithms and applications. Founda- tions and Trends& in Theoretical Computer Science, 1(2):117-236, 2005.
10

---

[15] Dapo Omidiran and Martin J Wainwright. High-dimensional subset recovery in noise: sparsified measurements without loss of statistical efficiency. arXiv preprint XXiv00805.3005, 2008.
[16] Galen Reeves, Jiaming Xu, and Ilias Zadik. The all-or-nothing phenomenon sparse linear regression. In Conference on Learning Theory, pages (652-2663. PMLR, 2019.
[17] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):27-8888 1996.
[18] Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using & connsttraieee quadratic programming (lasso). IEEE transactions on information theory, 55(5):2183-220,, 2009.
[19] Wei Wang, Martin J Wainwright, and Kannan Ramchandran. Information theooettc limits on sparse signal recovery: dense versus sparse measurement matrices. IEEE Transactions on Information Theory, 56(6):29772297, 2010.

---

Note that A Sparse Recovery using Sparse Measurements: Proofs
A.1 Proof of Theorem 1
Proof of Theorem
For any i E [n], we denote by X; == jeb) B, = (Big) jeln) N₁ ==
(NN)))e(p) We denote by S Supp (8*) the support of B*, Let S = {5 [p] ||| s}. We define the function:
L: - [0, +00)
S - | -1
where I denotes the vector in {0, 132 such that [1s]] = (j E 5) for all j E [p]. Note that, since X and Y are random, L(S) is a random variable for every 5 E S. In addition, note that:
L(S) = 1 + || (1s- - 1 2(2, X (Iss- 1s)) S
and, in particular:
L(S*) = 1212 Σ z
i=1
Fix S E S such that M = |S 1S 2 ös, and let U = \ S, V = =5 -588
S*.
[U] = V M. We define:
A = L(S) - L(S*).
Proposition A.1. As Asn.p,sdd 400:
'20²p" åds
n/2
P(A < 0) v
e co(n)
Proof. See appendix A.I.I
Hence, we obtain:
PP - X1ss12 - Y - X1s. [2) S (2000) n/2
co(n)
(16)
ōds
for any S E {0,11 1)" such that |S| = and IS A S*1 2 28s.
Using T6p and the union bound over the set of supports S s.t. I > 20s, we obtain:
Px,2 Supp (3*) A Supp
3
< 28s
2 Px,z
||Y - X1 > |Y X1 12 VS: ISAS 2 26.
= 1 - Px,z
33S: ISAS1 2 25s, I - x1 < I - X1ss 112)
U.B.
2 1
Σ
Px, (| - X1 و| 1/22 < I - x1s
$: S 1228s
202p
n/2
2 1
(n)
ods
First regime: = o (p). Using the Corollary of Stirling:
log s log (p/s) (1))
in the RHS of the inequality above, we obtain:
Px,2 (|Supp (1*) A Supp (8) < 25s)
2 - exp
log (p/s) (1 0 (1))
n
log
5ds
) +o(1)]
2
2002p)
12

---

Let slin = log(da/p)
2s logglo//p// (p/s)
(og(0/ Then if n 2 (1 +
Milin for some constant E >> 0, we have:
Fx,2
Suup (8*) A Supp (8)
20s)
(1+ 7
ôds
oxp
llog (p/s) (1 + o
log
+0(1))
2
20²p/
1
exp
slog (p/s) (1) log (ds/p) + log (2
=(1)
exp
s log (w/s)
( (-++0
Hence, n,,,88 d
+
Fx,2
Supp (8*) A Supp
(8)
20s)
2 1 exp (- Es log (p/s) (s log (p/s))
1.
Second regime: 8 = op, E (0, 1).
Using the Corollary of Stirling:
log
p
ph (a) (1 (1)),
we get:
Px.z (Supp (8*) A Supp (9) < 20s
2 1 - exp ph (a) (1 (1))
n1
log
ōds
+ +o(+)]
2
202p/
Similarly above, we take Minn
2H(
If 2 (1 + E) niin for some constant & >
log d log(da/(20"))
then we obtain, as p. 8, + +00:
Px,z Supp (3*)) A Supp (8) < 20s) 2 1 - exp -- ch (1x-x(p-hhh()) (a)p -1
1-expp
concluding the proof.
A.1.1 Proof of Proposition A.1
Proof of Proposition A.7
We have:
A = L(S) L(S*)
| (1ls 1s)11 +2 (1s. -1s))
Σ 1s - 11s +2 Σ Z (X, 1s. 1s)
1=1
We denote by (Ai)ie(m) the terms of the sum in the above expression, that is:
A; (X,, 1g.
1s)² (Z, lls- 1s).
Note that (A:) are i..d. and = Σm A, Now using the Chernoff bound:
P(A < 0) = P 0) inf (c 2 1) S inf M M-a. (0)". 820
(17)
820
We now study the moment generating function of A,, i.c. M- (-). We have:
M-A, (0)
Ex,2,
(x 1g) +2, 1s))
Ex;
e 11 10)²EZ, 10 18) X
e P(X. -.N.1s--1s7' 11) M2,1x, (-20 (01,,111-- 1s- - 1s))
Ex,
1(x.1s 19) ( (-2( -
Ex,
C 0+207 o) (X... - 15)
Ex;
( (-0220 2) (2 X1, - sser Xas)
Ex,
13

---

Plugging this expression into 17 we obtain:
log P A - 0) - n inf log Ex, [el (e(-04208=)) (Exer N
N Ejev xxx)²]
020
Studying the function 0 + - 20 on Rzo leads to the change of variable:
[c(-0+2080r (E X., -,yvv x
inf log Ex, 820
(18)
log Lx, e (Eser Xix Eser Xz)²].
inf OEL 0E(-00.1/(822]
(19)
One can check that the function 0 log Ex; (e-O(Zsco Xes- Miy--scc X.,) (-oo, (8o?)]- Hence (9) is equal
is non-increasing over
log Ex; (Esev Xos-xxxxeee X1y) (s))))
Therefore, the Chernoff bound yields:
(Csev Xey-Iievv X1,) /,,)/xx)////)) 1800))
log PP (A 5) S n log Ex,
(20)
Since UnV- Ø, have:
Σx.,
Xxy+
Σ
Σ Xij.
JEU
JEV
jEUUV
Therefore:
(Eee X.; -Eev X&) ((80))
(Eeetiv X,) ) (100))
= E
(Esetov Big N,y (Bor)
E
EB,
EN,
(Eyevuv N.y N /
B.
Eisuuv Miy Visceur 1a
Eiceur Meg B0
EB;
EN;
B:
In addition, conditionally on Bi, we have:
2
r Ejenov BijNij
d x1))
ExEOUY By
Its MGF is:
E [T B: M1JB, (1) v1 21
for l < 1/2.
Hence:
Excuvr B1gNy EEjeoo Bij
Eiryuy Big
[]eeor Bij 802
EB.
EN,
e
B,
EB,
Mrip.
2x
=En,
10 + ΣjEvUV Big LV
Let U180j and Visa) respectively denote the sets of 8s smallest elements of U and V. Note that this definition is legitimate since |U|
VV
M ds. Since Bij for all E U UV. we have:
Σ B N
Σ
B
JEULV
14

---

and hence:
20
20
Eg,
EB.
102 + Σjecuv Bij
V + +Zjet Big
Therefore, we get:
E e (Eseu Kis Eyev x.s) (802)) EB.
2a
402 + +ZjEUjauuu Bij
and plugging this into 20 yields:
20
log P A I n log
EB,
(21)
v 10 + EjEeionuMoo Big
Now note that, for any E [n]]:
Bij Bin 20s, d
p
(V)
In addition, since d = (p) and ds/p + too, have:
Lemma A.1. For any E [m]. the following holds: as p + +00,
Σ
Big 2ōds/p
dist N (0,1).
2
Proof.
The proof is simple adaptation of the proof of the Central Limit Theorem. See appendix
A.1.
Hence, there exists choice of the underlying probability space and random variables (Bis)sejn))jEb)) for which the random variable above converges almost surely and:
N =
lim +00
Σ
Bi 28ds/p
~ (0,
/
(EUlen
The above yields:
20
20
VA02 Ejel(nnMon
Bij
/ 402 + 28ds/p+ + /2dds/pN + to (Vdds/p)
Let:
20 /o/da/p
Vp
V422 EnEUjonuUAn Bij
Then we have:
20 ds/p
VP
4a2 28ds/p
/28ds/p N o (ds//p)
2a
28 + ds/p
N + 11/ ds/p 26 dspp
Since ds/p t00 as p > +00, the above yields:
20
20
V
/28
8
In addition, note the following:
15

---

Lemma A.2. Vp is uniformly integrable, that is: there exists p' E N such that
lim sup E [V [[//>TT]] = 0. T + p22
Proof. See appendix A.1.3 Therefore, get:
'202
lim
E Vpl
V
8
Hence, we write:
2a
202p
( p
ds
-1/2
EB,
to
402
Lio Bis
8ds
We conclude:
20
log P (A $0) S nlog
EB,
102 + -Ejetjen (io
Bis
2 p
((05)
ds
n log
to
ôds
p
2022p
(1 + (1))
log
+ log
dds
202pp
n
log
+ +0(1)
ōds
2222p
nnogog
+ o(n),
dds
which yields the desired result:
(20²p
n/2
P(A S 0) <
co(n)
ôds
A.1.2 Proof of Lemma A.1
Proof of Lemma A.I Let:
N₂
Σ
Bij - 28dd/8d
/ 20ds/p
16

---

Its characteristic function writes:
& Nr (t)
E [
it /26d//p
it. / (2ds/p 28
E
exp
26s
it 26ds/p
d/p + d/pexx
(it/ 20ds/D)
26s
e i 26ds/p
1 d/p
exp (it 2dds/p))
-1)
26s
t2
it
e
it 26ds/p
1+
40ds/2 / +
22dds/p
(2öds/p)
3/2
26a
E
it 26dz/p
1+
V20ds/D
it
4dds/p
t²
(2öds/p)* 3/2
1
it
t²
exp
-ity 28ds/p + log
1+d/p
20ds/p
4ōds/p
+0
(2ods
//dds/p3//
3/2
it
/6dd//p exp
2ds d/p
il.
12
0
/25ds/p
40ds/p
(2ōds/p)
3/2
sp
1
26d
exp
/ 2öds/p + it 20ds/p -12/2
+0
22dds/p
p
exp (-1 (1)) " exp (-1/12) x
for all E I. The result follows.
A.1.3 Proof of Lemma A.2
Proof of Lemma
A.2 Fix T > 2. We have:
/ ds/p
20
V
402 + ExE((an)MaN Bij
28
202 ds/p
V
25 ds/p
N
+ 0
VddsA
By total probability, we have:
E [IV 1 11 (1V
TH E
[ (1V > N (dss/p) P ([ [N (dds/p) vA)
+ | N < - (ds/p) /41 P (N < - (ds/p)1/a) 1)))
Let
6 = 11 [1V
T N (ds/p) 1/5 P P(N - (ds/p)) 1M)
and
Eg = V T) N < (ds/p) /11 P P(N (ds/p) 11)
so that E [[V 1 TH = E + E. We address the two terms separately.
First case: N 2 - (ds/p)*
1/4
We have:
2
28
402 ds/p
ds
-1/4
+
N + o
2
/28
+ 0
ds/p
ds/p
dds/p
ds/p
17

---

The RHS above goes to 0 as - +oc, and therefore it is 2 -8 for large enough, say for all p 2 Pi for some p1 E N. Hence we have:
2a
2a
[V
V
V8
26
dsjp
24 ds/p
N
+
+
/ds/p
for all p 2 P1. In addition, this implies:
(22
20
((V > 11551
> >T}
v3
In addition, have:
PP N P(N2
(ds 1
which all together yield:
E S v
20
11
{
(33
20
> T
v5
Second case: N < - (dds/p)) 1/4 We have:
20 ds/p
1V/ V
dds/p
A02 + EiEUnnyMaa Byj
which also implies:
1 ( > T) < { dsspp Vds/p>T]= =1 T ds
TT-=
p
In addition, by Gaussian tail bounds we have:
PP (NN < -ds/p)) Se
ddsle
for large enough, say for all 2 P2 for some P2 E N. Therefore:
E2 S / ds/p
A-/F
T
ds
Jarin
Note that the term dds/p e Therefore:
is decreasing ds/p increases (we have ds/p> T > 2).
{
ds
Bg T E T/2 T/2
1
T
Te
-T/2 T/2
p
We hence conclude that:
20
{
20
V (
>
TH =
S
T
TTe
V8
V8
for all p' = Pı V P2. Therefore we have:
2a Vo
2x
(20)
20
sup E
V
(1V)) 7)
<
1
> T }
+ TT12
v8
p2r'
This holds for any T 2. Taking T to +o,, the result follows:
lim sup E [
(VV) > T) =0 0.
T + p2H
18

---

A.2 Proof of Corollary 2
Proof of Corollary
2
This proof relies on bringing together Theorem T with the following result
from Wang et al.
19
Theorem (Necessary condition sparse ensembles, Corollary of 19)
the measurement
matrix X _x be drawn with i..d. elements from the following distribution:
N (0.2) 0,
X
w.p. w.p. --
for all i E [m], j E [p];
(22)
where E (0, 11. Let and
Cp. (A)= = BER
(Supp (3)
min (apppp())
|8:
2
Assume that o² Then, in the regime where 7s8 + +o0, a necessary condition for asymptotically reliable recovery over the signal class Cp.s (A) is given by:
log
2 log (1 + sA²)
Note that, while Theorem 4 is not stated on the exact same signal space Cp.s (A) in 19 but rather on the larger:
|8,1 2 1
R
[Supp (5) s, min
(ESupp(
follows directly from their result on "restricted ensembles" where the signal components under consideration are set exactly to À (see section III.A. in 19 ). We now proceed to prove Corollary 2
(i) We show that (7) holds using Theorem 4 but this requires adapting our problem to the framework used by Wang et al. in [9].. fact, note the model used Theorem 4 is different from the one we use in this paper, that defined in (5) In their model, Wang et al. 119 rescale the non-zero components X by multiplying them by 1/V7, and require that the noise variance o² 1. Therefore, we cannot directly use Theorem f in 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 N (0, o² In). can be equivalently written as:
Yo Xo + Zo.
where:
Yo 1 Y, Xo X,
dd/p Br, and Zo =
1 - ~ N L))
35
dd/p
Hence, it is particular case of the model defined in 22 with:
= d/p and
In addition, the regime we consider of d = w (p/s) corresponds exactly to the regime considered in Theorem where 7s - too. Therefore. using Theorem 4 a necessary condition for an asymptotically reliable recovery of 3* in the considered regime given by:
log (?) -
2 log (P) log + ds/ (po2)) log (ds/p (1 (1)).
log (*) -
(23)
7 log (1 + sX2)
19

---

First regime: s = o (p).
Using the Corollary of Stirling:
P
log
log (p/ss)
$
the necessary condition
23
writes:
2s log (p/s)
(1 + 0 (1)).
log (ds/p)
Let:
2s log (p/s)
SP INF
log (ds/p)
Assume there exists such that S (1 2) niST. We know that, for large enough n. d we have:
2s log (p/s)
n (1 e) INF
log (ds/p) (1 + o
which contradicts the necessary condition. Therefore, it is informationthhooetiialll theoreticallly impossible to ensure a reliable recovery of the support of 3**.
Second regime: op.
Using the Corollary of Stirling:
P) $)
log
ph (1+
the necessary condition 23
writes:
2h (a)p
(1 + (1))
n
log d
Let:
2h (a:) p
SP IN
log d
Similarly to above, we conclude that if there exists > 0 such that n < (1 8) iNF then it is teemmattoonthhoorticalll impossible to ensure a reliable recovery the support of 3r,
(if) We show that (ii) holds using Theorem
First regime: 8 = o (p). Let 8 > 0 and:
2s log (p/s)
niin
log (ds/p) + log (8/(202))
Note that:
2s log (p/s)
SP INN
Alin (
log (ds/p)
Assume there exists E such that n 2 (1 + <) SP Then:
+1) o (1)) niin
(1 + o (1)) 2 (1 (1+ e/2)
for n. P, 8, d large enough. Using Theorem
we have:
Px.z
1
Supp
(8)
A Supp (8*)
5
2 exp (- log (p/s) o (s log (p/s)))
2s
Therefore, we obtain:
Px, z
Supp
( A Supp (B*) <8)
2s
n. 8, d +00. Since this holds for all 8 0, we conclude:
Supp
i A Supp (8*)
- 0,
2s
in probability, n, d +00.
20

---

Second regime: = ap.
Let 8 > 0 0and:
2h (a)p
Plin
log + log (ōa/(20²) (202))
Note that:
2h (a)p
"INF
minn (1 (
log d
Assume there exists such that 2 (1 +) niNF Then:
n Σ (1 +1 (1)) -inn = +1+ (1+ nin 2 (1+ (1+E/2)
for n. p, 8, d large enough.
Using Theorem 1 we have:
Px,2
Supp
3
A Supp (8t) <6) 2 ( (
2s
Therefore, we obtain:
Supp ( A Supp (B*) <δ) 1,
Px,2
as n, 8, + +00. Since this holds 0 0, we conclude:
Supp
A Supp (B*)
2s
in probability, as n. p.p, - to0.
A.3
Proof of Example 2.2
Proof of Example 2.2
We have d = min (1 (o (1b (p)))), hence:
--
flog d/ logp= (1) ④ (d) (p) (11
In addition:
n1 = TIN = (p/ log
n12 = "INF (p//logd)
SP
Therefore, we have:
72
+ (p/ log d)
log log
+ (p/ log
=
w (1),
711
On one hand, the number of samples required for reliable recovery is better in the dense case:
n = (p/ log p) = olp/ log = o (n2).
(24)
On the other hand, the computational cost of recovering the support is better in the sparse case. In fact, matrix-vector multiplications are made easier by sparsity: the dense case, multiplying X with vector in Rº costs:
nip O(p2/ llggp)
real number multiplications, while multiplying X₂ with vector in IR costs
nzd θ (pd/ log d) ( (d)) ( (p) o(p² log (nip),
(25)
real number multiplications. computational cost.
This highlights the trade-off between sampling complexity and
D
21

---

B Improving Sparse Recovery via Sparsification: Proof of Theorem 3
Proof of Theorem
Let S {8 E [p]: |S| s}. We define the error function:
L: S - 00 +00)
S , y X1 8
Note that:
2
L(S) =
Y X1s
d Y X1.
p
2
d (X1s +2) X11
P
_ X1s- X1s -/2
d
p
In particular, we have:
d 2
L(S*)
x 1s. + -2 p
Let S E S. We define (S) = S* \. 8, B (S) = S' (S) == S* ns and M (S) = |A|
[B] = 1St S /2. Note that |C| = 8 - M. We are interested in bounding the following probability:
P (I) (.S)) - 0)
Note that the term above only depends on S through M. In fact, for any 8,S' S such that IS A | SS A I we have (S) _ (S"). In light of this, we define family of random variables (A (n)) msE[e] indexed by the rescaled symmetric difference 1j = M/s as L (S) - L (S*)
for some S such that |S ST 2M, that is:
For any 7 E
E [s]]
A (n) = L for some S s.t. ISA S* = 27ss.
We extend the notation above to r) E [0, by defining A (n) = A [ma1]]
Proposition B.1. Let 1) (0, 1] and S S such that S S [17)]. For any 0 (0, +00), define:
7 (0) = 2d /p².
Let E 13" denote random vector such that Bj lt the following random variables:
Ber (d/p). For any 0 E (0, 200), we define
ot (0, 02
Σ Bj. JEA(S)UB(S)
o (0, B) = 4d2s + ( (1+ 4d(1+ +7))
Σ Bj JEA(S)
2
P
Bij +4 (1-1-2
2d
+ (1 (01)
Σ
Σ B₁, JEC(S)
p
SEB(S)
Cov(u.y) (), = 0 (1+7100
2d
Σ B, (0))
Σ Bj
JEA(S)
JEN(S)
COvIU.V) (0, B)
(),
OU (0, (),B) oy (0
22

---

In addition, for any 0 E (0, +o0) we define the random variable:
if
ac (C. - p(0, 1,
f B0, =
ou(0.B)ov(0.BB) (( -pl.,,,,,__((()))))) (1it)))vossa000))
+.00
else.
(26)
Then we have:
inf EB |s (0, B)))
(T) 0)
050
Proof. See section B.1
Now recall that and are both linear in In particular, there exist a, 16 E (0, 1) such that:
$ = ap d = upp
We have:
(0) = 2d0022
fof0o02/p² /p² =
2026600
(27)
Proposition B.2. We define:
22 4
C
+))) > 0.
vb
Define the function:
E: N
(0, +00)
C* (1)
p 20rppp
Consider the random vector E (0, Bj lid Ber (1b). define the random variable:
H, (B) = f (g (p), B).
Then the following hold:
(i) Hp (B)
[+10CC-M) as + +00.
(ii) ( (1) < 0) EB [Hp (B))
Proof. See section B.2
Conjecture B.1. The exists such that (Hp (B)))2po is uniformly integrable, that is:
lim sup E, H, (B) (H, = =0.
T p2ro
Hence we have Hp (B) as.
which by Conjecture B.1 yields:
(+)p
lim Eg H, (B) = too
1+ 1+0*** (n)
Therefore, we obtain:
Ep [H, (B) = V
1 Cp (n) +0(1).
23

---

Thus, by Proposition B.2 we have:
log (P (n) = 20)
- log
EB [Hp (B))
1
=
log
(V
m+++ (n) + +0(11)
log
(1+
mpC (n)) + +0(1).
2
Hence:
-n/2 edn) (() 50) < mpb (m))
Taking the union bound:
P Supp (B*) A Supp ( < 20s
2 P ||/ X1s
y X1l
VS: | 2 =2ss)
2 20s, ||
-X11 $ || - X11s 1
1 P
3S: ISA S*1
Σ
P ((p
X1s]
X1s
12 1 y - X1s 12)
8: 1226
Σ
Σ
(S) $
WE (i/s: (E(+)):
8: ( 2ms
Σ
Σ
P(A (1) 50)
(1/a/ (E(4
92
(8AS 2qs
Σ
(1+ (7)
-n/2 (n))
2 1
neli/e: rE(s)): n26
In addition, we have:
Σ
(1 + mpC" (n))-n/²
Σ
8v (1+600" (8)) -n/2
(1+
(28)
(E/s/s: rE(s)): 728
ne (i/s: (E(+)): 926
< s (1 + S (8)) (8))-n/2 -n/2
(29)
where 28 holds because the term inside the sum is non- non-increasing in 7, and cardinality of the index set of the sum is upper bounded by s. Therefore:
29h holds because the
P ( (|Supp (3*) A Supp (8)
< 20x)
P
+ 500 (6) -n/2 (n)
2 1
8
ph (a) (1 + o (1)) + log s - n ( ( [olo (1 (1+6000(6) + +o(1))
= 1 exp
(a( (1+) - n (t) log (1+ oyp (6)) + +o(1)]
1 exp
We define:
2h (h(
log 11 + 8 (6)
24

---

Let > 0. Then if n 2 (1 + E) n", we have:
P Supp (8*) A Supp (8) <26s)
(2l0g log (1+ (+5000(0)
+o(1)]
2 1 exp ph (a) + (1+
1 exp ph (p)( (-8+
p +0000 1.
B.1 Proof of Proposition B.1
Since y and S are fixed, we will simplify notations in this proof as follows: we will write A for A (1). and A, B, C, M respectively for A (S) B (S), C (S), M (5). We have:
Proof of Proposition B.
A ((S)- - I((5))
d X1g. X1s + Z
( d X-
1g. + d oz
2
X- -X)
2
p 1
[1s|] |2 - -||81s-
2
d
+2
(X1l + 2 (1g. - -lss)
2
Σ Xi,, 1s)²
(Xx, 1s +2 d
Σ
(( 1s.) + Zi) (1X1, Is-) - (Xis Ls)
p i=l
2=1
Σ (X 1s) 11)) (X., 1. + 2 ((x, 1s.) + 2i) ((x,, 1s.) - (8x, -8x:11s))
Let:
A = (X,, 1s) - (X, 1s +2 +2
d ((,,, 1s)) + Zi) (1x,)
1s.)) - -(X,, - (8),
So that
A Σ A, Now using the Chernoff bound:
P < 0) = TP (-A 0) = inf TP (e 00 2 1) S inf M (0)"
(30)
820
820
We have:
A = (Xi, 15) - -Xi,, 1s.) )2
+
((x,, 1s.)) + 2i) (Xt 1s.)) - (Xi, 1s)
p
2
2
Σ X13
EX,
Σ X
+2
d
Σ JES'
X + -s
X [xx=
Σ
Σ Xi
p
1E8
JES
jESt
jES
Σ
X
Σ X1s
Σ
X
Σ
Xii - 2 d
Σ Xij
Xij
p
JEST
JES
JES.
JES
JES.
+ Zi
Σ
X
Σ X
p
JES
JES
Then:
4
Σ X1I
Xis
ΣX.
X
Σx,
+2 Σ
X.j -2 2 d
Σ Xij
p
YEA
BEB
jEA
JEB
jEC
jES
+ d Zi
Σ
X
ΣX1,
P
JEA
JEB
25

---

Let:
)
(Σ
X.j -2 d
K; :=
Σx,,
Xig
Σ
Xix
Σ
X.y +2 Σ
Σ
Xij.
jEA
JEB
JEA(S)
JEB(S)
JEC(S)
p
jES
so that:
d Zi A = +2
Σ
E
P
iEN
jEB
The MGF of -A; can be expressed as:
M-A, (0) E /exp
K; +2 2 d
= B.
Ez,
exp
-0
- Zi
Σ
Xij-
-
Exi
Xx. Bi
P
jEA
jEB
2d0
= =Rx,,
AK R2z
exp
Z4
Σ
Xij
Σ
Xig
X;, B
P
JEA
JEB
= -
e
AK: Mz. X.,.
2d0
Σ
Xij
Σ
X
P
JEN
jER
2
2d0
= Ex,,B
e AK: exp
Σ
X
Σ
0²
2
P
ij
jEA
JEB
2
2020222
= Ex,B, exp
-OK; +
Σ
XIJ
Σ
Xis
p2
/EA
JEB
Thus, by the tower rule:
1
2028202
M_A, (0) = EB,
Ex.
exp
-0K,
Σ
ΣX13
Xis - Σ
Xes
B.
(31)
D2
JEN
JEB
Fix 0 > 0. Then:
20
OK +
- X
-
Σ
D2
iEN
jEB
Xig -2 d
0
Σ
X11
Σ
Xis
Σ
XIs +
Xij +2 Σ
Σ Xij
p
JEA
JEB
JEA
jEB
jEC
jES
20
Σ
X
Σ
X
122
JEA
JEB
0
Σ
Biy
Σ
Xij
x
YEA
JEB
Σ
(1+7 B.g
2d
Xij + Σ (1-7(00)
B,y
+2 Σ
Bij
d)
x.y
p.
p
jEA
jEB
jEC
26

---

where y (0) - 2a2002 /pp. Since @ is fixed for now, we simplify the notation y (0) by simply writing
y. Let:
U= 0 (Ejea -Xx--EjED Xy)
V== EJEa (1 Big 2d) p
Xij + 1jEB(1
(1 -
Bi +2Σ (Be, -+) -/)xx Xis
so that:
2
22 pd
OK +
Σ
X1
Σ
Xij
= UV.
(32)
JEA
JEB
Plugging (32 in (3), we obtain:
M-A. (0) = EBB [x. [e |
(33)
Note that, conditionally on B;, we have:
U - N 0, E
Σ BB
(34)
JEAUB
and:
v VEN 0, 1
(1+ Bij
2d 2
=
+ Σ
(1-
7)
B + Σ
Bij
)
a)
2
(35)
p
JEA
JEB
JEC
Let:
oi 0 E, EJEAUB By
of oZ= = Ejea (11 (1+ Big 2d) + E) (1- + Excc (B.g - 2
Note that:
att = 6 Σ
Bij.
JEAUR
and
oi = E
(1 (1+ Big
2d
+
Σ(1 (1-7) 7) B3 +4 Σ
Bij d)
p
p
jEA
jEB
JEC
4d (1 + 7)
4d
Σ jEN
(1 (1+ B3
Bis)
+
M + Σ
(1 7) B3
p
p2
jEB
2d
+ 1d
+4 44)
B
-
Bis
(MM
(s M)
p
p2
JEC
4
Σ
(1 (1+
4d (1 (1+))
Bij Σ (1 - (1- 2 Bij +4
(1
2d
Bij
p2
P
p
JEA
JEB
jEC
+ (u+n2²
4d 4d 7)
Σ
Bij + ( (1-
Big + + (1 (1-
2dl
Σ
Bij-
D2
P
p
JEN
JEB
jEC
In addition, we have:
Cov (OV(U,))= =0 | (1+7) Bij
2d
Bij - Σ (1 7) Big
jEA
JEB
(1147 - 2d
=1
Σ
Big - -1- Σ Bij
p
JEA
JEB
27

---

Lemma B.I. Let Ni & N (0, N₂ - N (0, and p corr (N1, N2). Then:
if 0.o0 p > 1,
E [e
else.
Proof. See section B.1.1
Now using Lemma B.1 with Gaussian random variables and V, we conclude that:
Ex, [eev] B:] (0, B:),
(36)
with f (+ defined in 26 Plugging this into 33 we obtain:
M-A. (0) EB, [f (0, B.)]
(37)
Let B E 10, be random vector such that Bj Lid. Ber (d/p). Note that B B,. Then 37) yields:
M-A, (0) = Eg [f (0, B)].
Plugging this into the Chernoff bound 30 we conclude:
inn Ep [ (6, B)] " 000
P P S 0) -
B.1.1
Proof of Lemma B.1
Proof of Lemma B.1
We have:
[e No
-f
ey
1
2
y
y
2
ZER yER 2 exp
2p
+
dydr
2 p²)
01
02
02
1
y
y
exp
2p
dydæ
JZER YER 110100211-0 12
2 (1 p²)
01
02
02
x2 2pry y²
2ZER YEB 2T 1-pp p2
exp
01020y
2 211 - p²)
dydr
2 p²) ZER YER
exp (20102 (1 (1-p² p²²) ry x² 2pry y²2 dydr
2T /
p2
p²
exp (20102 (1 0²) xy - x² + 2pry - y²) dydx
ZEB
YER
Therefore:
[e N1No
1 2
o² dydæ
π
ZER yER
1- 1
(1-=(((((11 +-² (( dyda
ZER yER
V1- 1 1
(1000)1--))))) (0- dydæ
ZER
VER
V1- P
(0100 (1)0)( / V 2
dydr
ZER
/1 11-10 D
exp (3² ((1102 (1 x²) +p)² +-)=-=1)) Vīda.
ZEE
28

---

Hence we obtain:
B B[eMiNNa]= V1 11-pi p²
JEER
J exp
(2²
(1-
dr.
V
Let 0102
1²=p²)++ + p. Note that, f 2 1, the above explodes to +oc. However, i < the
above yields:
VI- p²
R NiN]
exp (x² (52-1)) de
ZER
V1-#* P
exp (-x²) dx
VTVI-
DER
V1 p²
VT 2 (NT011/V3) (x) dr
VTVI e
V1 p²
V1 -
Plugging the expression & in the above, we obtain:
V1 p2
E c N1N2
V 1 02 -0703 (1 02)²- -2p - 0102
1
v1 03 (1 p²) -2p0102
1
VI+ + poof0 - 2p 0703
V100102 - 1)2 - 0/
1 )
0102 -p) -1
In addition, note that:
<<l + 0102 (1- (1-p²) +
0102 (1 + p) (1 - p) <1-p
0102 (1 + p) <1
1
1
0102 p.
B.2 Proof of Proposition B.2
Proof of Proposition B.2 Fix 17 (0, To simplify notations, we will write C* instead of C* (7))
All asymptotic statements are as + +o0.
We start by showing (i). First, note the following.
Lemma B.2.
Σ By m1 +0))), ((rr)()+0(1)). JEA(S)
By nord JEB(S)
Σ
By (1 on/ + o1)) JEC(S)
Σ
Proof. See section B.2.1
29

---

Next, plugging the expressions given by Lemma B.2 into the expressions of oj (6. B). oy (6, B) and Cov(u.v) (8, B) given in the statement of Proposition B.1. we obtain the following.
Proposition B.3. We have:
ot (0, B) = 2npanppf (1 + 01))
of (6, B) = 2ompp (2 - 2 + (8)) -(1 - w)²] (1 (1+)
(U. (6, B) = 2n02ppp (7 (0) 2/) (1 0(1)
Proof. See section B.2.2
Plugging & (p) in the expression of 7 (+) given by (7). we obtain:
20- o²800* = 0 (1).
7 (E)) = 2x)
200p
op
Therefore, we have by Proposition B.3
( at (D) B) (z) B) 2
C'
2 (2 24p + 11 ((v) - (E)))) - (1 -))) (1+))(++))))
+0
20mpp/
= n 2 - 24/ + 1) (1b - 0 - 2
(-}))) -(1
(1+0
= m/c (2 - -22 + 17 (2 - 1)) (1+
no:2( (2 2xb + 2070 n)
Note that the above is > 0 because 77 (1 2 < - 1)), which follows from the facts that 17 S 1
and di E (0, 1). In addition, by Proposition B.3
C* ())
Cov (E B)) 2naop
2aup
n (0()) 1)) (1+)
n.s -n000
Bringing these together, we obtain:
{11- {1-Coorcer) Cov(o.r) (E(),, B))3 (o) (E()), of (v), B) + 1 1+ )
lim 7-0000
= 2 - 17(2 (0(2-22 21h + 2mph c)(²²= - -
Cu2 +2mo0' + 1 n7( 2 2 2mp - n) 0²2 - mpcC -1
(122022 2n + 271 - 217²'/ 3 n7¹ c22 + mpc
C
-(1 (1 ()) (2 17 (1 x) 0*
= 0.
30

---

In addition:
2
lim p-0000
ou ov (E) - (p)) B)
1- Cov (5 (E()), B)
lim p-++00
ou (E(P)) B) (E()),
(1+
( 2Φ + 27p0 -11 11 17)
(1 (1+m00*) mp00+* ) - -n(2 2-1b + 21p0 - 1) C*2
=1 =1 +
n/ 2 + 2n 17 C+2
+ m/C
=1+
(1 [1+ m++++ - -11+
=1+
TPpC" > 1.
Therefore, there exists p' E N such that, for all 2 p' we have:
ou (E))), B) (E(P), B) p(E(p), B) 1.
Then note that, for all p 2 p' we have:
ou (E ov (5 (E()) B) p (E)
and hence:
[ (p), B)
ou (z), (E(,), V
(ooVElo) - (p) B)
1
Covru.y (E()) B)) oi (p) of (B) B)
a.S.
1+ M²C**
Therefore, we conclude that holds. We now show (ii). We have: inf Eg f (8, B)] s Eg f (E (p), B) = Eg (H, (B)).
820
Plugging this into the Chernoff bound obtained in Proposition B.I we obtain:
[in EB [1 (0, B))" " < [ [1, (B))" " 000
F 0)
B.2.1
Proof of Lemma B.2
Proof of Lemma
B.2
We know that Bj lid Ber (1)). Therefore:
Σ
B, (S)) + VIA(S) + CO (VIA
JEA(S)
where NA ~ N (0. 1). In addition, we have:
IA (S) [ns] = 175(1 +o (1)).
31

---

Hence:
E JEA(S)
By - coobp(++0(1)
Similarly, we have:
Σ JEB(S)
B, - =o==nopp1+-000 +
and
Σ JEC(S)
Bj = (1 (1pp)
B.2.2
Proof of Proposition B.3
Proof of Proposition
B.3
We have by Proposition B.1
o (),
B) = 0²
Σ
Bj
JEA(S)UB(S)
4d3s
(1= 4d(1+
o4 (0, B)
Σ Bj
p2
P
jEA(S)
+ (1 (1-7 Σ
Bij + (1-
2d
Σ Bj,
p
SEA(S)
jEC(S)
((14-10)-
2d
Cov (0, =
Σ
Bij - 7()) Σ
Big
JEA(S)
jEB(S)
Now by Lemma B.2
we have:
E EsEA(S) Bj p
Σ DjBB()) B, = -noup(1 -
Σ EjEC(S) B, =(1 (1-1)) (1)))))))))))
Hence, the expression of oz (0, B) writes:
of (0, B) = 0² Σ
By+ + 0
Σ Bj
JEA(S)
JEB(S)
8² noakp
+ (1) + 8² @
+
2n (1+0
32

---

The expression of of (0, B) writes:
oi (6.B)
4d
(1++-10)²² 4d(1 +
Σ By
1²
P
jEA(S)
Σ Bij 4 (1 (1-
2d
+ +11-7
Σ Bj
p
JEB(S)
jEC(S)
44n p (1 + (6)) (1 + (0) - 41)) moupp + (1))
+ +1 (acp((--0()) + +
(1-
44 + (00)))))))) (0) + +4 - 26) (1- (n) (1+
amp
aep
4 4v + 7 +0)++++0)++1111-1111))1
4 ( (0) - 4( - 20)) (1+
ppp
4- 4/ + n ( (2> +4 (0) 1)
40h (0)
-4)) (1=
-4))
2 - 2 + 7 (7(()) 207 (0) (0) 26 - 11 (1 (1+)
2app
2 21h + 1 (7)) 2007 (0) 3/2 1/ + 246 - 1)) (1 (1))
=20/p
2 2 + n (w) 1000--7000 (0)) - -1- (1+
2avp
The expression of Cov (0, B) writes:
Coveu.v) (0, 0 1 (1+ 2d Σ
=m)
Big - (1-7(0)) Σ Bij
p
jEA(S)
SEA(S)
(11 24/) (1
+ +1)) - -11 (10)
narppl (1++700- 22d) ((1- (1+0
2naopp0 (0) - (1 (0)1+((11) (1)),
as desired.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Theorem | Corollary 2 and Theorem Saaeeem@cca clearly state the main claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations where discussed:
Briefly the introduction (section
Thoroughly in Remark 2.2 and Remark 3.1
Future work directions in the conclusion (section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Complete proofs of theoretical results are provided: for Theorem in appendix
in
A.1 for Corollary appendix AA.2] for Example 2.2 appendix A.3 and for Theorem
in appendix B
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments. In order to observe our results we need the dimension of the problem to be large, which cannot be ran experimentally since computing the MLE (33) exponential-time
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
35

---

reproducible, they (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code. with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpps//nnis.cc)
jublic/guidde//ooeeuuppii http://odeeuuiiissiooooooooooooo ssionooicyy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurlPS code and data submission guidelines http://cccccb.ccguueeeee///////e
for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
36

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The main positive societal impact of our work is reducing computational cost in range of applications via the measurement sparsity vs. computational cost trade-off. Applications of the sparse recovery problem are discussed in the introduction and an example of computational cost reduction is given in Example 2.2
37

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets geg., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets. Previous theoretical results are properly credited to their authors.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
38

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, [paperswi thcode. wwt.cooo/caaa. da has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets. We provide our interpretation of the theoretical results in sections 2 and
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
39

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval. you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMS if an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
40


Reviews:
[{"review_id": "cfGGe3E299", "reviewer": "Reviewer_LvPh", "summary": "This paper studies sparse signal recovery under the sparse measurement matrix assumption. The paper shows an information-theoretic sample complexity threshold for successful sparse recovery, i.e., the phase transition happens at $n^{SP}_{INF}= \\Theta(s\\log{(p/s)}/\\log{(ds/p)})$ where d is the non-zero entries of the measurement matrix, s is the non-zero entries of the signal and p is the dimension of the signal. Furthermore, the paper shows a simplified sample complexity for a specific regime where $s$ and $d$ is asymptotically proportional to $p$.", "questions": "Besides the issue I mentioned in above, I would like a summary table that compares the sample complexity for different cases among the previous work and this paper.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: The problem set up (i.e., the sparse measurement assumption) looks interesting. The result in Theorem 1 looks solid and can be related to previous work.\nWeakness: The major concern I have is around the assumption of $\\sigma^2=\\Theta (1)$ and therefore are dropped in later results (e.g. Corollary 2 and Theorem 3). The noise level $\\sigma^2$ plays a very important role in SNR and SNR is the major key component (if not the most important)  that determines how difficult the recovery problem is and thus how much sample would be roughly needed.\n If we assume $\\sigma^2=\\Theta (1)$, then $SNR \\rightarrow \\infty$ when $ds/p \\rightarrow \\infty$ which is an easy task. Previous works that study the linear problem under asymptotic regime mostly need to control $SNR=\\Theta(1)$ or at least the results depend on $||\\beta^*||$ or $\\sigma^2$ so that we can derive the corresponding sample complexity when $SNR=\\Theta(1)$. For example, in [13] (referenced in this paper), the abstract points out that \"high signal to noise ratio $k/\\sigma^2 = \\Omega (1)$ regime\". In the light of this, I would recommend relaxing the assumption of $\\sigma^2=\\Theta(1)$ and revising the introduction and the results other than Theorem 1 accordingly.", "was_revised": true, "final_justification": "About infinity signal to noise ratio, I understand it is non-trivial even for case of infinite signal to noise ratio, I have preference for limited signal to noise ratio. Other comments look good to me. Therefore, I remain my score.", "rebuttal": "&#8202;\n\nWe thank the reviewer for their thorough evaluation. Below, we address their questions and concerns to the best of our ability. At the end, we note a slight improvement to our work that we will incorporate into the camera‑ready version of the paper.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Weaknesses:** The major concern I have is around the assumption of $\\sigma^2 = \\Theta\\left(1\\right)$ and therefore are dropped in later results (e.g. Corollary 2 and Theorem 3). The noise level $\\sigma^2$ plays a very important role in SNR and SNR is the major key component (if not the most important) that determines how difficult the recovery problem is and thus how much sample would be roughly needed. If we assume $\\sigma^2 = \\Theta\\left(1\\right)$ , then $\\mathrm{SNR} \\rightarrow +\\infty$ when $ds/p \\rightarrow +\\infty$ which is an easy task. Previous works that study the linear problem under asymptotic regime mostly need to control $\\mathrm{SNR} = \\Theta\\left(1\\right)$ or at least the results depend on $\\left\\| \\beta^\\star \\right\\|$ or $\\sigma^2$ so that we can derive the corresponding sample complexity when $\\mathrm{SNR} = \\Theta\\left( 1 \\right)$. For example, in [13] (referenced in this paper), the abstract points out that \"high signal to noise ratio regime\". In the light of this, I would recommend relaxing the assumption of $\\sigma^2 = \\Theta\\left(1\\right)$ and revising the introduction and the results other than Theorem 1 accordingly.\n\n\n&#8202;\n\n- **Rebuttal:** We appreciate the reviewer’s thoughtful concern regarding the assumption that $\\sigma^2 = \\Theta(1)$, which implies that $\\mathrm{SNR} \\rightarrow +\\infty$  when $ds/p \\rightarrow +\\infty$. We think of the sparse recovery problem as exhibiting two components of difficulty: a combinatorial component, consisting of identifying the correct support of $\\beta^\\star$ given a random projection $X \\beta^\\star$; and a statistical component, consisting of reliably isolating the signal from the noise. Intuitively, the assumptions of $\\sigma^2 = \\Theta(1)$ and $ds/p \\rightarrow +\\infty$ allow us to isolate the combinatorial component by making the SNR go to infinity in high dimensions. We note that *even* in absence of noise, namely when SNR is $\\infty$, identifying the correct support of the signal remains highly non-trivial, and is known, in the dense design setting, to exhibit phase transitions and fundamental hardness: see Gamarnik and Zadik [7] and Wang et al. [16] in our manuscript, as well as classical papers on compressive sensing such as \"Sparse nonnegative solution of underdetermined linear equations by linear programming\" by Donoho and Tanner and \"Decoding by linear programming\" by Candes and Tao.  \n   We agree that assuming a finite or vanishing SNR would make the setting more realistic in some applications. In that case, the recovery problem becomes more complex: one must not only identify the correct support, but also reliably isolate the signal from the noise. While this combined regime is indeed of interest, it is at this point beyond the scope of this paper. We believe our work provides a step toward extending these results to the finite-SNR regime, which is a valuable direction for future work. On the other hand, we acknowledge that it is important for the paper to explicitly mention that we are considering the high-SNR regime, and we appreciate the reviewer’s observation in this regard. We will clarify this point in the camera-ready version of the paper.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Questions:** Besides the issue I mentioned in above, I would like a summary table that compares the sample complexity for different cases among the previous work and this paper.\n\n\n&#8202;\n\n- **Rebuttal:** We thank the reviewer for this helpful suggestion. We fully agree that a summary table comparing the sample complexity across different settings would improve the paper. In the camera-ready version, we will add the following table summarizing the key information-theoretic and algorithmic sample complexity results from prior works alongside the new results presented in this paper.  \n   &#8202;  \n| Regime | Information-theoretic, Necessary | Information-theoretic, Sufficient | Algorithmic, Necessary | Algorithmic, Sufficient |\n|---|---|---|---|---|\n| Dense $(d=p)$ | $\\frac{2 s \\log(p/s)}{\\log{s}}$ ([13], [16]) | $\\frac{2 s \\log(p/s)}{\\log{s}}$ ([7], [13]) | $2 s \\log(p-s)$ ([7]) | $2 s \\log(p-s)$ ([15]) |\n| Sparse | $\\frac{2 s \\log(p/s)}{\\log(ds/p)}$ (Corollay 2, originally by [16]) | $\\frac{2 s \\log(p/s)}{\\log(ds/p)}$ (Theorem 1) | No result known so far |$2 s \\log(p-s)$ ([12])|\n\n&#8202;  \n\n---\n\n&#8202;  \n\nBesides the issues described above, we note the following slight improvement to our work, which we will incorporate into the camera‑ready version of the paper.\n\n&#8202;  \n\n-   ___Matching signal classes in Corollary 2 (Remark 2.2, first bullet point).___ Revisiting the proof of the necessity statement of Wang et al. [16, Theorem 2], we verified that the same Fano-based argument applies verbatim to show the necessity statement for binary signals, i.e. $\\beta^\\star \\in \\\\{0,1\\\\}^p$. In fact, at a high level, the authors show the necessary condition for $\\beta^\\star \\in C_{p,s}$ by first showing it for $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then adding that if no decoder can recover $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then no decoder can recover $\\beta^\\star \\in C_{p,s}$ (since $\\\\{0,1\\\\}^p \\subseteq C_{p,s}$), which weakens their result. This closes the gap between signal spaces, unifying both necessary and sufficient conditions for binary signals. In the camera‑ready version, we will restate the necessary condition of Corollary 2 for binary signals and remove the first bullet point of Remark 2.2. \n\n&#8202;"}, {"review_id": "DbLlloaMH3", "reviewer": "Reviewer_KJwa", "summary": "The authors study how taking a sparse measurement matrix in sparse regression (or compressed sensing) problems affects the sample complexity of these problems. Previous work showed that, at a given level of sparsity, recovery of the hidden signal is impossible with too few statements. This work shows a matching positive information-theoretic result, that above this number of samples the (computationally intractable) maximum likelihood estimator does asymptotically recover the (support of the) signal. Thus this result settles the information-theoretic threshold of sparse regression with a sparse measurement matrix. To account for the possibility that the measurement matrix is prescribed rather than designed by the user, the authors also prove a similar result (conditional on a technical conjecture) for a random sparsification of a given dense measurement matrix. That is, a measurement is *generated* with a dense measurement matrix, but *recovered* by a sparsification of that matrix.", "questions": "- Since the idea of sparsification is an algorithmic one and the precise means of sparsification is presumably flexible, could other ways of sparsifying a matrix rather than completely at random that have stronger guarantees on spectral properties they preserve be useful? This area has been widely studied with the advent of general-purpose matrix concentration inequalities, and for example many examples are discussed in Tropp's monograph \"An introduction to matrix concentration inequalities\".\n\n- What does \"slow decay of sparsity\" mean in regard to the computational threshold (p2), and could the authors be slightly more specific about the status of the algorithmic threshold? Is the algorithmic threshold for a sparse measurement matrix actually known, and known to be comparable to the performance of LASSO? I assume not quite, since (to my knowledge) the question of the overlap gap property under sparsity of the measurement matrix has not been addressed before?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The main result is well-motivated and a valuable addition to the literature on this subject that closes a clear open problem of pinning down the information-theoretic threshold for this problem. The authors clearly describe the state of affairs and their contribution, and the background information on the problem is presented very nicely and leaves (to me) no lingering concerns. The idea of sparsification is also a nice one and gives a valuable complement to the first main result about sparse measurement matrices. The authors are also very clear and explicit about even minor limitations and restrictions of their result, which I appreciated.\n\nWeaknesses: The proof techniques for analyzing the MLE are fairly standard, and it seems (though I have not gone through them in detail) that while sparsity changes things it does not make these calculations require fundamentally different tools. Also, a minor point: the introduction of sparsification is a little bit unclear, and I would present this problem in the way that I describe it in the summary, emphasizing that the point is to consider using a different matrix for measuring versus recovering.", "was_revised": true, "final_justification": "I did not raise any substantial issues but just a few clarifying questions, and the authors replied to my satisfaction. I am leaving my positive rating of the paper unchanged.", "rebuttal": "&#8202;\n\nWe thank the reviewer for their thorough evaluation. Below, we address their questions and concerns to the best of our ability. At the end, we note a slight improvement to our work that we will incorporate into the camera‑ready version of the paper.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Weaknesses:** The proof techniques for analyzing the MLE are fairly standard, and it seems (though I have not gone through them in detail) that while sparsity changes things it does not make these calculations require fundamentally different tools.\n\n&#8202;\n\n- **Rebuttal:** We appreciate the reviewer’s observation. While it is true that our proofs rely on classical tools such as the union bound and the moment method, the sparse setting introduces new technical challenges that go beyond those in the dense case. In particular, the sparsity of the design matrix breaks the Gaussian structure typically leveraged in the dense setting, requiring us to analyze more intricate moment generating functions. Most importantly, this involves studying transformations of Binomial random variables with means diverging to infinity, as seen in the proof of Proposition A.1, as well as Lemma A.1 and Lemma A.2. These challenges become even more pronounced in the second part of the paper (Section 3), particularly in the proofs of Proposition B.2 and Theorem 3 where the result remains subject to a subtle conjecture (Conjecture B.1) due to technical complications that arise from the Bernoulli mask used in sparsification. We believe that handling such complications is a meaningful technical contribution, and we thank the reviewer for highlighting the similarity to the dense setting in the use of traditional techniques.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Weaknesses:** Also, a minor point: the introduction of sparsification is a little bit unclear, and I would present this problem in the way that I describe it in the summary, emphasizing that the point is to consider using a different matrix for measuring versus recovering.\n\n&#8202;\n\n- **Rebuttal:** We thank the reviewer for the phrasing suggestion. We agree that framing the sparsification setting as using a different matrix for measurement versus recovery provides a  clearer perspective. We will incorporate this description into the camera-ready version of the paper to improve clarity.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Questions:** Since the idea of sparsification is an algorithmic one and the precise means of sparsification is presumably flexible, could other ways of sparsifying a matrix rather than completely at random that have stronger guarantees on spectral properties they preserve be useful? This area has been widely studied with the advent of general-purpose matrix concentration inequalities, and for example many examples are discussed in Tropp's monograph \"An introduction to matrix concentration inequalities\".\n\n&#8202;\n\n- **Rebuttal:** We thank the reviewer for these insightful suggestions. We view our work as a first exploratory step toward understanding the role of sparsification in signal recovery, rather than an attempt to close the question. In this paper, we deliberately focus on a simple and arguably naïve sparsification model (applying an i.i.d. Bernoulli mask after the dense matrix is observed) to introduce the question and highlight its fundamental challenges. This choice keeps the setting directly comparable (and technically equivalent) to the classical missing‑at‑random framework studied extensively in high‑dimensional statistics, see Loh and Wainwright \"High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity\" and related references. In the camera-ready version of the paper, we will highlight how our findings complement the existing missing-data guarantees and direct readers to these references.  \n   In general, the designer-dependent sparsification is an appropriate setting for signal processing, but less appropriate in statistical applications. From a pure sparsification standpoint, we agree that more sophisticated sparsification schemes -- particularly those designed to preserve spectral properties -- are a promising direction for sharpening recovery guarantees and improving empirical performance. We thank the reviewer for these great suggestions and believe they constitute an excellent direction for future exploration of the sparsification problem.\n\n&#8202;\n\n---\n\n&#8202;\n\n>- **Questions:** What does \"slow decay of sparsity\" mean in regard to the computational threshold (p2), and could the authors be slightly more specific about the status of the algorithmic threshold? Is the algorithmic threshold for a sparse measurement matrix actually known, and known to be comparable to the performance of LASSO? I assume not quite, since (to my knowledge) the question of the overlap gap property under sparsity of the measurement matrix has not been addressed before?\n\n&#8202;\n\n- **Rebuttal:** We thank the reviewer for their interesting question. By the “slow decay of sparsity” in line 82, we mean the assumption made by Omidiran and Wainwright [12]. This assumption is later stated in the equation following line 87, and can also be found in [12], equation (8c). Under this assumption, the authors show in [12, Theorem 1] that the sufficient condition under which the LASSO reliably recovers the signal in the dense case, notably: $n > (1+\\varepsilon) n_{\\text{ALG}}$, where $n_{\\text{ALG}} = 2 s \\log(p-s)$ is also sufficient, in the sparse case, for the LASSO to reliably recover the (signed) support of the signal. We believe this is interesting since it might suggest that the algorithmic threshold is insensitive to the sparsity of the design although, as far as we know, and as the reviewer mentioned, there are yet no negative results on the algorithmic threshold side, since the overlap gap property has not been addressed before in the sparse measurement matrix setting. To summarize, here is the current status of the algorithmic threshold, to the best of our knowledge:  \n\n   * ___Positive results:___ only known so far is by Omidiran and Wainwright [12, Theorem 1].\n   * ___Negative results:___ none yet.  \n\n&#8202;  \n\n---\n\n&#8202;  \n\nBesides the issues described above, we note the following slight improvement to our work, which we will incorporate into the camera‑ready version of the paper.\n\n&#8202;  \n\n-   ___Matching signal classes in Corollary 2 (Remark 2.2, first bullet point).___ Revisiting the proof of the necessity statement of Wang et al. [16, Theorem 2], we verified that the same Fano-based argument applies verbatim to show the necessity statement for binary signals, i.e. $\\beta^\\star \\in \\\\{0,1\\\\}^p$. In fact, at a high level, the authors show the necessary condition for $\\beta^\\star \\in C_{p,s}$ by first showing it for $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then adding that if no decoder can recover $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then no decoder can recover $\\beta^\\star \\in C_{p,s}$ (since $\\\\{0,1\\\\}^p \\subseteq C_{p,s}$), which weakens their result. This closes the gap between signal spaces, unifying both necessary and sufficient conditions for binary signals. In the camera‑ready version, we will restate the necessary condition of Corollary 2 for binary signals and remove the first bullet point of Remark 2.2. \n\n&#8202;"}, {"review_id": "0m9uopsXWW", "reviewer": "Reviewer_A45Y", "summary": "The paper studied the problem of support recovery of a sparse vector (signal) of dimension p from n linear projections, under the less common but interesting assumption that each projection vector is sparse (with d non-zero elements on average). In other words, support recovery of a sparse vector using a sparse sensing matrix. \nThe main results are:\n (1) A sufficient condition on the number of measurements guaranteeing recovery using the MLE in terms of p, d, and s (the number of non-zero entries in the signal) when ds/p-> infinity. Combined with previous results (Wang, Wainwright, and Ramchandran, 2016), this new condition yields an information-theoretic phase transition. \n (2) Sufficient conditions on the number of samples n when a dense sensing matrix undergoes a sparsification process.", "questions": "Referring to an extended setting outlined in Lines 67-68, it is unclear what sparsity means.", "limitations": "Yes. Especially in Remark 2.2.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The topic is within the scope of NeurIPS. \n- The motivation for considering a sparse sensing matrix to save computation is reasonable. \n- The contributions are significant.\n\nWeaknesses:\n- As the authors mentioned, the analysis in the paper leaves several challenges (mostly discussed in Remark 2.2). These challenges could probably be resolved with relatively little work, so it appears that a more complete work is within reach.\n- I suggest explaining in the introduction the connection between support recovery and MSE or other natural error criteria.  \n- There are a few undefined terms: H(\\alpha), ||s||_0, in the abstract, it is unclear that n_{inf}^{sp} refers to the number of measurements,", "was_revised": true, "final_justification": "The authors provided satisfactory replies to my question and addressed the weaknesses I raised. \n\nThe author's response strengthens my opinion to accept the paper.", "rebuttal": "&#8202;  \n\nWe thank the reviewer for their thorough evaluation. Below, we address their questions and concerns to the best of our ability.  \n\n&#8202;  \n\n---\n\n&#8202;  \n\n>- **Weaknesses:** As the authors mentioned, the analysis in the paper leaves several challenges (mostly discussed in Remark 2.2). These challenges could probably be resolved with relatively little work, so it appears that a more complete work is within reach.\n\n&#8202;  \n\n- **Rebuttal:** We thank the reviewer for their comment on the limitations of our work. We note the following about the limitations described in Remark 2.2.  \n&#8202;  \n\n   1. ___Matching signal classes in Corollary 2 (Remark 2.2, first bullet point).___ Revisiting the proof of the necessity statement of Wang et al. [16, Theorem 2], we verified that the same Fano-based argument applies verbatim to show the necessity statement for binary signals, i.e. $\\beta^\\star \\in \\\\{0,1\\\\}^p$. In fact, at a high level, the authors show the necessary condition for $\\beta^\\star \\in C_{p,s}$ by first showing it for $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then adding that if no decoder can recover $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then no decoder can recover $\\beta^\\star \\in C_{p,s}$ (since $\\\\{0,1\\\\}^p \\subseteq C_{p,s}$), which weakens their result. This closes the gap between signal spaces, unifying both necessary and sufficient conditions for binary signals. In the camera‑ready version, we will restate the necessary condition of Corollary 2 for binary signals and remove the first bullet point of Remark 2.2.  \n   &#8202;  \n\n   2. ___Inconsistency of the notions of \"reliable recovery\" in necessity and sufficiency statements (Remark 2.2, second bullet point).___ In line 197, we mistakenly described Reeves et al. [13] as proving exact‑support recovery (i.e., equality of supports). In fact, they study a random binary signal model (uniform over $s$‑sparse supports) and assess the performance of a decoder via MSE relative to a random‑guess baseline. They show an all‑or‑nothing transition: for $n > (1+\\varepsilon) n_{\\text{INF}}$, the MLE achieves strong recovery in the sense that the ratio of its MSE to the random‑guess MSE tends to $0$; while for $n < (1-\\varepsilon) n_{\\text{INF}}$, no estimator can asymptotically perform better than a random guess. In particular, they show convergence of the expected rescaled symmetric‑difference error to $0$. By contrast, Theorem 1 in our work establishes convergence in probability of the normalized symmetric difference for each fixed signal. Thus, their guarantee is expectation‑based under a random‑signal model, whereas ours is probability‑based under a fixed‑signal model. Finally, although their proof relies on the Gaussianity of the entries of $X$, which breaks down in our sparse setting, we believe the gap between their expectation guarantee and our high‑probability guarantee can be closed in the sparse‑measurement setting with more refined tools similar to those in our proof of Theorem 1, especially since the same sequence of proofs happened in the literature of the dense setting. For the same reason, we believe a similar negative result to the one shown by Reeves et al. [13] can be shown in the sparse setting. In the camera-ready version, we will correct Remark 2.2 accordingly.  \n   &#8202;  \n\n    With the above modifications of Remark 2.2 in mind, there aren’t any challenges anymore in the first part of the paper. Our work and the work of Reeves et al. [13] constitute two slightly different problem setups, with different error metrics and recovery guarantees. While in our problem setup the recovery guarantees we obtained using our error metric did not allow us to use the same notion of \"recovery\" in the necessity and sufficiency statements, Reeves et al. [13] obtain (in their problem setup and using their error metric) recovery guarantees that allow a single notion of \"recovery\", which yields a cleaner phase transition. As mentioned above, we believe that a result similar to theirs can be shown in the sparse setting. However, that would constitute a completely different work, which we leave for future exploration.\n\n   &#8202;  \n\n   Finally, concerning Conjecture B1: it's about a uniform integrability statement, the proof of which we believe is a tedious task due to the complications that arise from introducing the binary mask of sparsification on one hand and from the bias in the rescaled observations (discussed in lines 279-286 of the manuscript) on the other. We believe the proof of Conjecture B.1 would be a far more technically involved sparsification-version of the proof of Lemma A.2.\n\n&#8202;  \n\n---\n\n&#8202;  \n\n>- **Weaknesses:** I suggest explaining in the introduction the connection between support recovery and MSE or other natural error criteria.\n\n&#8202;  \n\n- **Rebuttal:** We thank the reviewer for their helpful suggestion. Since the signal is binary with fixed sparsity, our error metric (the symmetric difference; see Definition 2.3) corresponds exactly to the squared $\\ell_2$-loss. Specifically, for any $s$-sparse vectors $\\beta, \\beta^\\star \\in \\\\{0,1\\\\}^p$, we have $ \\mathrm{|} \\\\ \\mathrm{Supp}(\\beta) \\\\ \\Delta \\\\ \\mathrm{Supp}(\\beta^\\star) \\\\ \\mathrm{|}  = \\mathrm{||}\\beta - \\beta^\\star \\mathrm{||}\\_2^2$. Thus, Theorem 1 can also be interpreted as a high-probability guarantee on the convergence of the rescaled squared loss (per non-zero coordinate).  \n    In our work, we focus on binary signals as a simplifying assumption. While this setting is representative, sampling complexity guarantees for support recovery in this class can typically be extended to the class of signals whose non-zero components are bounded away from $0$ by $1$, i.e. $\\min_{j = 1,\\dots,p} |\\beta_j^\\star| \\geq 1$, with the same thresholds.  \n    Moreover, sparse linear regression can naturally be reduced to support recovery since, once the support is identified, the full signal can be estimated via the closed-form expression of the maximum-likelihood estimator given by $\\beta_{\\text{MLE}} = X_{S^\\star}^{+} Y$, where $X_{S^\\star}^{+}$ denotes the Moore-Penrose pseudoinverse of the submatrix of $X$ restricted to the support $S^\\star = \\text{Supp}(\\beta^\\star)$. We agree with the reviewer that these clarifications are valuable and will include them in the introduction of the camera-ready version of the paper.  \n\n&#8202;  \n\n---\n\n&#8202;  \n\n>- **Weaknesses:** There are a few undefined terms: $H(\\alpha)$, $\\mathrm{||} s \\mathrm{||} \\_0$, in the abstract, it is unclear that $n_{\\text{INF}}^{\\text{SP}}$ refers to the number of measurements.  \n\n&#8202;  \n\n- **Rebuttal:** We agree with the reviewer on this weakness and thank them for pointing it out. In the camera-ready version of the paper, we will:\n    * Add to the abstract a clarification that $n_{\\text{INF}}^{\\text{SP}}$ refers to the number of measurements.\n    * Add a “Notation” paragraph at the end of the Introduction (Section 1) to clarify some notations like the entropy function $H(\\cdot)$ and the $\\ell_0$-norm $\\mathrm{||} \\cdot \\mathrm{||}\\_0$.  \n\n&#8202;  \n\n---\n\n&#8202;  \n\n>- **Questions:** Referring to an extended setting outlined in Lines 67-68, it is unclear what sparsity means.\n\n&#8202;  \n\n- **Rebuttal:** We thank the reviewer for asking for clarification. In the extended setting (lines 67-68), \"sparsity\" continues to mean having exactly $s$ non-zero components, i.e. $\\mathrm{||}\\beta^\\star\\mathrm{||}\\_0 = s$. The only change is that we now allow each non-zero coordinate to take an arbitrary real value of magnitude at least $\\lambda$, replacing the binary constraint $\\beta^\\star \\in \\\\{0,1\\\\}^p$ by $\\beta^\\star \\in \\\\{ \\\\ \\beta \\in \\mathbb{R}^p \\\\ \\colon \\\\ \\min_{j \\in [p]} |\\beta_j| \\geq \\lambda \\\\ \\\\}$. Equivalently, $\\beta^\\star \\in \\\\{ \\\\ \\beta \\in \\mathbb{R}^p \\\\ \\colon \\\\ \\mathrm{||}\\beta\\mathrm{||}\\_0 = s, \\\\ \\min_{j \\in [p]} |\\beta_j| \\geq \\lambda \\\\ \\\\}$. We will add this explicit statement to the text in the camera-ready version to remove any ambiguity.  \n\n&#8202;"}, {"review_id": "9aAZRtjY3D", "reviewer": "Reviewer_qyQw", "summary": "The paper studies sparse recovery with the added structure that the design matrix itself may be sparse (i.e. sparse measurements). The authors derive the information-theoretic threshold which delineates the sample complexity for when asymptotic support recovery of the signal is possible/impossible. Under a certain conjecture, the authors also describe how one might sparsify a dense measurement matrix and still obtain signal recovery; this can be useful from the standpoint of storage and computation resources.", "questions": "- The authors are transparent about the gaps. Though it may not be possible to quickly resolve them, I think it would substantially improve the paper if the authors could describe, even at a high-level, what the difficulties are in closing the gaps. Such a description would be helpful in convincing even the skeptical reader that the issue is not so serious (as the authors believe).\n\n- The authors need to acknowledge and cite the missing data literature, as this is very closely related to the sparsification considered in the latter part of the paper. For example, the authors need to discuss Loh & Wainwright, \"High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity\" as well as discuss related references.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "__Strengths__\n\nThe paper studies a canonical setting and the problem of studying sparse measurement matrices is very interesting. The problem is clearly of interest to the NeurIPS community, and the paper provides interesting practical implications as well. The paper's main result, a sharp characterization of the price of sparsity, is quite fundamental and nicely explains to what degree information in the measurement matrix is important. The writing is very clear, and the arguments are transparent. I especially appreciated the proof sketch of Theorem 1. The paper is also very honest about its limitations. I enjoyed reading this paper.\n\n__Weaknesses__\n\nIn my view, the only weaknesses of the paper are the ones the authors themselves identify. Strictly speaking, the upper and lower bounds are not directly comparable since they apply to different settings. Yet I, like the authors, don't believe the gap is fundamental and could be closed. Of course, it does weaken the ultimate conclusions of the paper. Specifically, the conclusion of Theorem 1 + Corollary 2 cannot be interpreted as a strict characterization of the information-theoretic threshold. As the authors note in Remark 2.2, the parameter spaces between upper and lower bounds are different, and the notion of recovery is also different. Likewise, the results regarding sparsification are conditional on a conjecture. It would be really great to have all this cleaned up (especially concerning Theorem 1 + Corollary 2), especially for a top venue like NeurIPS. However, I am sympathetic to the authors and also am willing to speculate the gap is not fundamental.", "was_revised": true, "final_justification": "The authors have addressed the gap that I noted in my comments, and so I have increased my original score (5 to 6).", "rebuttal": "&#8203;  \n\nWe thank the reviewer for their thorough evaluation. Below, we address their questions and concerns to the best of our ability.\n\n&#8203;  \n\n---\n\n&#8203;  \n\n>- **Weaknesses:** In my view, the only weaknesses of the paper are the ones the authors themselves identify. Strictly speaking, the upper and lower bounds are not directly comparable since they apply to different settings. Yet I, like the authors, don't believe the gap is fundamental and could be closed. Of course, it does weaken the ultimate conclusions of the paper. Specifically, the conclusion of Theorem 1 + Corollary 2 cannot be interpreted as a strict characterization of the information-theoretic threshold. As the authors note in Remark 2.2, the parameter spaces between upper and lower bounds are different, and the notion of recovery is also different. Likewise, the results regarding sparsification are conditional on a conjecture. It would be really great to have all this cleaned up (especially concerning Theorem 1 + Corollary 2), especially for a top venue like NeurIPS. However, I am sympathetic to the authors and also am willing to speculate the gap is not fundamental.\n\n&#8203;  \n\n- **Rebuttal:** We thank the reviewer for their comment on the limitations of our work. We note the following about the limitations described in Remark 2.2.  \n&#8203;  \n   1. ___Matching signal classes in Corollary 2 (Remark 2.2, first bullet point).___ Revisiting the proof of the necessity statement of Wang et al. [16, Theorem 2], we verified that the same Fano-based argument applies verbatim to show the necessity statement for binary signals, i.e. $\\beta^\\star \\in \\\\{ 0,1 \\\\}^p$. In fact, at a high level, the authors show the necessary condition for $\\beta^\\star \\in C_{p,s}$ by first showing it for $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then adding that if no decoder can recover $\\beta^\\star \\in \\\\{0,1\\\\}^p$ then no decoder can recover $\\beta^\\star \\in C_{p,s}$ (since $\\\\{0,1\\\\}^p \\subseteq C_{p,s}$), which weakens their result. This closes the gap between signal spaces, unifying both necessary and sufficient conditions for binary signals. In the camera‑ready version we will restate the necessary condition of Corollary 2 for binary signals and remove the first bullet point of Remark 2.2.  \n&#8203;  \n\n   2. ___Inconsistency of the notions of \"reliable recovery\" in necessity and sufficiency statements (Remark 2.2, second bullet point).___  In line 197, we mistakenly described Reeves et al. [13] as proving exact‑support recovery (i.e. equality of supports). In fact, they study a random binary signal model (uniform over $s$‑sparse supports) and assess performance via MSE relative to a random‑guess baseline. They show an all‑or‑nothing transition: for $n > (1+\\varepsilon) n_{\\text{INF}}$, the MLE achieves strong recovery in the sense that the ratio of its MSE to the random‑guess MSE tends to $0$; while for $n < (1-\\varepsilon) n_{\\text{INF}}$, no estimator can asymptotically perform better than a random guess. In particular, they show convergence of the expected rescaled symmetric difference error to $0$. By contrast, Theorem 1 in our work establishes convergence in probability of the normalized symmetric difference for each fixed signal. Thus their guarantee is expectation‑based under a random‑signal model, whereas ours is probability‑based under a fixed‑signal model. Although their proof relies on the Gaussianity of the entries of $X$, which breaks down in our sparse setting, we believe the gap between their expectation guarantee and our high‑probability guarantee can be closed in the sparse‑measurement setting with more refined tools similar to those in our proof of Theorem 1, especially since the same sequence of proofs happened in the literature of the dense setting. For the same reason, we believe a similar negative result to the one shown by Reeves et al. [13] can be shown in the sparse setting. In the camera-ready version, we will correct Remark 2.2 accordingly.\n\n   &#8203;\n\n   Finally, concerning Conjecture B1: it's about a uniform integrability statement, the proof of which we believe is a tedious task due to the complications that arise from introducing the binary mask of sparsification on one hand and from the bias in the rescaled observations (discussed in lines 279-286 of the manuscript) on the other. We believe the proof of Conjecture B.1 would be a far more technically involved sparsification-version of the proof of Lemma A.2.\n\n&#8203;  \n\n---\n\n&#8203;  \n\n>- **Questions:** The authors are transparent about the gaps. Though it may not be possible to quickly resolve them, I think it would substantially improve the paper if the authors could describe, even at a high level, what the difficulties are in closing the gaps. Such a description would be helpful in convincing even the skeptical reader that the issue is not so serious (as the authors believe).\n\n&#8203;  \n\n- **Rebuttal:** We thank the reviewer for this interesting question. With the above modifications of Remark 2.2 in mind, there aren’t any gaps anymore. There are two slightly different problem setups, with different error metrics and recovery guarantees. While in our problem setup the recovery guarantees we obtained using our error metric did not allow us to use the same notion of \"recovery\" in the necessity and sufficiency statements, Reeves et al. [13] obtain (in their problem setup and using their error metric) recovery guarantees that allow a single notion of \"recovery\", which yields a cleaner phase transition. As mentioned above, we believe that a result similar to theirs can be shown in the sparse setting. However, that would constitute a completely different work, which we leave for future exploration.\n\n&#8203;  \n\n---\n\n&#8203;  \n\n>- **Questions:** The authors need to acknowledge and cite the missing data literature, as this is very closely related to the sparsification considered in the latter part of the paper. For example, the authors need to discuss Loh \\& Wainwright, \"High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity\" as well as discuss related references.\n\n&#8203;  \n\n- **Rebuttal:** We thank the reviewer for pointing this out. Sparsification is indeed closely related to the \"missing covariates\" model studied in the high‑dimensional regression literature. We will add a short discussion and cite Loh and Wainwright, \"High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity\", and subsequent work on noisy or missing data. Their results provide algorithmic $\\ell_2$ and $\\ell_1$ error bounds for dense Gaussian designs with a constant missingness rate, whereas our work focuses on information‑theoretic support‑recovery thresholds: we allow the missingness rate to grow (via $d$ or $\\psi$), and quantify the exact price of sparsification. In the camera‑ready version of the paper, we will highlight how our findings complement the existing missing‑data guarantees and direct readers to these references.  \n\n&#8203;"}]

Author rebuttal:

Meta-review: ### Summary
This paper studies sufficient conditions for successful support recovery of a $p$-dimensional $s$-sparse signal using its noisy linear measurement with a sparse matrix (with $d$ non-zero elements per row). Together with the necessary condition reported in [16] (reproduced as Corollary 2 (i) in this paper), the result of this paper states that in the two regimes $ds/p\to\infty$ and $ds/p\to\tau\in(0,\infty)$ the problem exhibits a phase transition at an information-theoretic criticality in the number of samples. As a second contribution, this paper stidies support recovery of a sparse signal using noisy linear measurement with a dense matrix, while a *sparsified* version of the measurement matrix is to be used in recovery. A sufficient condition for successful support recovery for this setting (Theorem 3) is obtained, under a certain integrability conjecture.
### Strengths
- The subject is clearly of interest to the NeurIPS community.
- The problem setting of considering a sparse measurement matrix is of practical significance.
- This paper is well written and well organized.
### Weaknesses
- There remain small technical gaps (difference in the signal models, as well as exact versus approximate recovery, as well as integrability conjecture), which have been explicitly mentioned in the main text (Remarks 2.2, 3.1).
### Reasons for decision
The rating/confidence scores from the four reviewers were 4/3, 5/4, 5/4, and 6/4, all being on the positive side, with the average 5 well above the threshold of acceptance. A majority of the review comments were clarifying ones, and overall, the author response seems to have successfully addressed those comments on unclear points raised by the reviewers. Because of these, I am glad to recommend acceptance.
### Additional points
- Line 162: the set (of) supports
- References:
  - Capitalization is not coherent throughout the reference list.
  - [9]: The bibliographic information seems imcomplete.
  - [15]: using (*\\ell*\_\{1\} → $\ell_1$)-constrained
Decision: Accept (poster)