Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
Authors: Arya Mazumdar
Neha Sangwan
Venue: ICML 2025 poster (2025)
Keywords: sparse linear regression
one bit compressed sensing
sparse recovery
Primary area: theory->everything_else

Abstract: We consider the problem of *exact* recovery of a $k$-sparse binary vector  from generalized linear measurements (such as *logistic regression*). We analyze the *linear estimation* algorithm (Plan, Vershynin, Yudovina, 2017), and also show information theoretic lower bounds on the number of required measurements. As a consequence of our results, for  noisy one bit quantized linear measurements ($\mathsf{1bCS}$), we obtain a sample complexity of $O((k+\sigma^2)\log{n})$, where $\sigma^2$ is the noise variance. This is shown to be optimal  due to the information theoretic lower bound. We also obtain tight sample complexity characterization for logistic regression.
Since $\mathsf{1bCS}$ is a strictly harder problem than noisy linear measurements ($\mathsf{SparseLinearReg}$) because of added quantization, the same sample complexity is achievable for $\mathsf{SparseLinearReg}$. While this sample complexity can be obtained via the popular lasso algorithm, linear estimation is  computationally more efficient. Our lower bound  holds for any set of measurements for $\mathsf{SparseLinearReg}$ (similar bound was known for Gaussian measurement matrices) and is closely matched by the maximum-likelihood upper bound. For $\mathsf{SparseLinearReg}$,  it was conjectured in Gamarnik and Zadik, 2017 that there is a statistical-computational gap and the number of measurements should be at least $(2k+\sigma^2)\log{n}$ for efficient algorithms to exist. It is worth noting that our results imply that there is no such statistical-computational gap for $\mathsf{1bCS}$ and logistic regression.

Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements
Arya Mazumdar'
Neha Sangwan
Abstract
1. Introduction
Sparse linear regression and compressed sensing have been topic of intense research in statistics and signal process- ing for the past few decades (Candès al., 2006; Donoho, 2006; Tibshirani, 1996; Do Ba et al., 2010). The prob- lem of binary sparse linear regression (SparseLinearReg) considers linear measurements of an unknown binary vec- tor, corrupted by additive Gaussian noise. Focusing on binary signals, this particular problem has recently been studied in (Gamarnik Zadik, 2017a;b; 2022: Reeves et al., 2019), mainly motivated by the question of support recovery of sparse signals (Wainwright, 2009). Formally, for an unknown k-sparse signal x E 10, sensing ma- trix A E IR=x*" and a noise vector = (Zı, Zm) where 2,8 are iid NNO0, o2) for some variance o², we observe given by
We consider the problem exact recovery of k-sparse binary vector from generalized lin- ear measurements (such logistic regression). We analyze the linear estimation algorithm (Plan, Vershynin, Yudovina, 2017), and also show in- formation theoretic lower bounds on the number of required measurements. As a consequence of our results, for noisy one bit quantized linear measurements (lbCSbinary), we obtain a sample complexity of ((k + o²) logn), where o² is the noise variance. This is shown to be optimal due to the information theoretic lower bound. We also obtain tight sample complexity characteriza- tion for logistic regression. Since lbCSbinary is strictly harder problem than noisy linear measure- ments (nea because added quan- tization, the same sample complexity achiev- able for SparseLinearReg. While this sample complexity can be obtained via the popular lasso algorithm, linear estimation is computationally more efficient. Our lower bound holds for any set of measurements for SparseLinearRes (simi- lar bound was known for Gaussian measurement matrices) and closely matched by the maximum- likelihood upper bound. For SparseLinearReg conjectured in Gamarnik and Zadik, 2017 that there is statistical maaistical-comppuaationa gap and the number of measurements should be at least (2k + o²) log n for efficient algorithms to ex- ist. It is worth noting that our results imply that there is no such statistical-come computiialll gap for
= A
(I)
Our goal is to design the (possibly random) sensing matrix A with power constraint, i.e.,
[[(ATx)] k, m,
where A; denotes jth row of the matrix A and the expecta- tion is over the possible randomness in A, and a decoding algorithm ø such that
XC (0.1) 1 X/, - P(O(A,)) + as n (3)
max
Here, |x|H denotes the Hamming weight x E {0, 13" The probability computed over the randomness of sensing matrix and the (randomized) algorithm.
1bCSbinary and logistic regression.
The problem of one bit quantized linear measurements (also known one bit compressed sensing (1bCSbinary)) is sim- ilar, except that the output vector y is the sign of Ax + instead of the entire vector Ax + z (Boufounos & Baraniuk, 2008). That is, we observe
'Halicioglu Data Science Institute. University of California San Diego, La Jolla, United States. Correspondence Neha Sangwan <nchasangwanO10e gmwillcomm...............
y = sign Ax z).
(4)
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Here, y = (y...... Vm is defined as ys = sign sign(A, 21), E m) where sign(a) = 2 and sign(a)

---

Exact recovery of sparse binary vectors from generalized linear measurements
otherwise. An algorithm o' for 1bCSbinary takes input y and A. Again, we require that"
As corollaries, we obtain tight sample complexity characterization for noisy one bit compressed sensing (Corollary 2.2 and Corollary 2.6) and logistic regres- sion (Corollary 2.4 and Corollary 2.7).
max XE (E(1))"" 1x
P yA x x) + 0 as nl oc.
(5)
The algorithm can be used for SparseLinearReg ei- ther directly (Corollary 2.3) or by first quantizing the received signal to its sign value and then using the algorithm for 1bCSbinary. The sample complexity is the same for both these cases. This shows that in the regime where the number of measurements are at least C(k + o²) log n for some constant C, keeping only the sign information sufficient for LnarseL.nearReg.
Usually in I-bit compressed sensing, the Gaussian noise before quantization is not present. Our formulation can be considered as sparse "probit model" (McCullagh, 2019).
More generally, we define the problem of generalized linear measurements (GLMs). e-g. (Kakade et al., 2011; 1; Plan et al., 2017) where we assume that the observation y = (yi..... Vm) is related to the sparse binary input vector x using "inverse link" function g such that for each E [m]]
We provide "almost" matching information theoretic lower (Corollary 2.8) and upper bounds (Theorem 2.9) for exact recovery in SparseLinearReg. If the mea- surements are Gaussian, we get slightly better lower bounds (Theorem 2.10).
E | A.] g (A?x).
(6)
That is, the expected value of the output yi is linked to A; only through A/ x. For example, for SparseLinearReg
E [y A,x,
A summary of results in presented in Tables 1, 2 and 3.
for 1bCSbinary
1.1. Discussion of results and related works
-AA
E [MA|A,]= 11 2Φ
Intuitions on lower bounds. Observe that 1bCSbinary is strietly more difficult problem than SparseLinearReg in the sense that any algorithm that works for 1bCSbinary can be used for SparseLinearRRe by using only the sign information. Thus, the sample complexity of 1bCSbinary is at least as much as SparseLinearReg, the latter can be much smaller in some cases. From an information theoretic viewpoint, randomly chosen k-sparse vector has entropy log (*) ~ k log F. Since each y can give at most one bit of information, we need at least & log & measurements for 1bCSbinary (See Corollary 2.6 for the exact lower bound) to learn x. For put has infinite precision. In fact, we can show that in the absence of noise, only one sample is sufficient to recover the unknown signal (see Remark 1.1). SparseL can be viewed as a coding problem for a Gaussian channel, where x is the message and Ax is its corresponding codeword. Thus, from the converse for Gaussian channel (see (Cover & Thomas, 2006, Theorem 9.1. we need at least llg(n/kk C
where & is the Gaussian cumulative distribution function. In the logistic regression model (LogisticRegression), we observe binary output y/ E 1 for each measurement i E [m]. The probability that takes value is given by
py== 1) 1te 1+e-8a"x 8a"x
for parameter 8 > 0. The parameter 3 controls the level of noise. When 3 + oo, the model approaches noiseless one bit compressed sensing. As 3 decreases, the output becomes more noisy. When 3 = 0, the output uniformly distributed on { 1} and is independent of x. In this model,
on the other hand, the out-
E [B [ tanh BATx
2
Our contributions. In this paper, our contributions are the following:
samples for exact recovery. Here C' is the capacity of the Gaussian channel, which depends on SNR (a function of Ax and d²). Given the power constraint of Eq. (2) (which is satisfied when entries of A are chosen iid (( 1)), the ca- pacity C' is 1/- log (1 + ) thereby showing that the lower hound for SparseL can be much smaller.
We analyze the linear estimation-prooection algorithm (Plan et al., 2017) for generalized linear measurements of sparse binary inputs (Theorem 2.1). We also provide an information theoretic lower bound (Theorem 2.5).
Binary sparse linear regression. The problem of binary sparse linear regression was introduced in (Gamarnik & Zadik, 7a; 2022) and was further studied in (Reeves et al., 2019). An "all or nothing" " phenomenon was shown in (Reeves et al., 2019) for approximate recovery of binary vec-
'The probability of error measured by (5) corresponds to the 'oor each' criterion in the one bit compressed sending litera- ture. The 'for all' criterion which requires that the same sensing matrix works for all unknown signals corresponds to showing (Ex such that ø ('A,y) y) # x) + as n oc.
2

---

Exact recovery of sparse binary vectors from generalized linear measurements
tors at the critical sample complexity of m² 2 2k log n/k
from (Matsumoto & Mazumdar, 2022)) when specialized to exact recovery for binary sparse vectors requires ( (by choosing = 1/vk). On the other hand, our bound is O(k log n)) This discrepancy is because the previous models are studied for the "for all" model which is a harder problem than our present "for each" model. The results in (Plan et al., 2017), on the other hand, are for the "for each" model, though their analysis is not optimal for binary vectors (see Appendix B). The problem of noisy one bit compressed sensing (IbCSbinary) introduced here is moti- vated by the probit model (e.g. see modern treatments of the non-sparse probit model (Kuchelmeister & van de Geer, 2024)). Here we provide an information theoretic lower bound of m 2 (k+ + o²) log (n/k) and show that the afore- mentioned efficient algorithm (Algorithm 1) works with the same m O(k + o²) log n) samples and has a computa- tional complexity of O(kk + o²) log n.). We also provide optimal sample complexity characterization for learning binary sparse vectors under the logistic regression model, which was previously studied for learning real vectors (Hsu & Mazumdar, 2024; Plan et al., 2017).
) showing that approximate recovery is possible if and only if m 2 m.. It was additionally conjectured in (Gamarnik & Zadik, 2017a) that no efficient algorithms exist in the regime m" Σ Malg - (2k + o²) log n. When m 2 malg. various algorithms like Lasso (Wainwright, 2009), Orthogo- nal Matching Pursuit (OMP) (Tropp & Gilbert, 2007) and (Ndaoud& & Tsybakov, 2020) can recover the sparse vector. It has also been shown in (Gamarnik& & Zadik, 2017b) that lasso fails to recover unknown vector x when m S emaalg for some small constant c. Outside this regime, local search algorithm was proposed (Gamarnik & Zadik, 2017b), which starts with a guess of x and iteratively updates it.
log :>)
In (Reeves et al., 2019), the information theoretic lower bound of m is shown for the case when each entry of the sensing matrix is chosen iid N / 1). We consider the exact recovery guarantee for the problem and show that m 2 m" samples are necessary even when the sensing matrix is not Gaussian (Corollary 2.8)². We show an almost matching upper bound based on the Maximum Likelihood Estimator (MLE) using a random Gaussian sensing matrix (Theorem 2.9 and Theorem 20). This is along the lines of the MLE analysis in (Reeves et al., 2019), which was done for approximate recovery (our sample complexity for exact recovery turns out to be slightly different).
Algorithm for binary vectors. We consider a simple algo- rithm which is equivalent to the "average algorithm" (Serve- dio, 1999) or "linear estimator" (Plan et al., 2017), followed by selection of the 'top-k' coordinates. Regarding the intu- ition behind the algorithm, signal x, the output y and As,, the restriction of the sens- ing matrix to columns where x is 1, are correlated whereas y and A (1s are uncorrelated. Here, (1:x),,s denotes the restriction of the sensing matrix to columns where x is O. Thus, we compute the inner product between y and each column of the sensing matrix as a proxy for correlation between the output and the corresponding column. The output of the algorithm is the top k-most correlated columns (See Algorithm 1 for details.). One can also think of this as a "one-shot" version of the popular OMP algorithm. This algorithm requires O((k + +o²) log n) samples for 1bCSbinary and SparseLinearReg and O(k++1(1)) log n) for LogisticReeression. It has computation complexity of O(k + a )²)n log Most of the previous algorithms, in- cluding the one in (Plan et al., 2017), were given for the case when the unknown signal is not necessarily binary. It should be noted that the black-hox application of the result of (Plan et al., 2017) specialized to binary inputs will not recover the optimal sample complexity. See Appendix B where we show that the results in (Plan et al., 2017) imply sample complexity of O(k2 log (2n/k)). We provide simple yet optimal analysis of the sample complexity in our special case of sparse binary signals.
Remark 1.1. It was observed in (Gamarnik & 7adik, 2017a) that in the no-noise regime (o² = 0), one measurement is sufficient to recover the underlying vector by brute force. However, it is conjectured that there is no efficient algorithm if m S 2k log n. The results in (Gamarnik & Zadik, 2017a) were shown only when the entries of the sensing matrix are chosen iid (00 1) (i.e. Gaussian design). For arbitrary sensing matrix, an efficient way to recover x using only one measurement is by using A = 2- [1, 2, 22,,..,,,2"" 2n_1.. Note that 2nh x y in this case is the value of unknown signal in the decimal system (base 10). can be converted to binary in Onn) time. This suggests that for specific non- random constructions, there may be efficient algorithms in the conjectured hardness regime.
observe that for unknown
Binary one-bit compressed sensing. The problem of one bit compressed sensing has been well stud- ied e.g. (Boufounos Baraniuk. 2008: Jacques et al., 2013) including greedy algorithms (e.g. (Liu et al., 2016)) and noisy test outcomes (c.g. (Matsumoto & Mazumdar, 2024)),
and the problem of recovering binary vectors has also been studied in (Acharya et al.. 2017; Mazumdar& & Pal, 2022).
However, these works do not consider the Gaussian noise prior to quantization. The best known upper bound (O(k/e)
Our lower bounds hold for a weaker average probability of error recovery criteria, instead of the maximum probability of error in Eq. (3). However, for random Gaussian sensing matrix both criterion can be shown to be equivalent.
We would like to emphasize that the sample complexity of Algorithm 1 for both SparseLinearReg and 1bCSbinary is the same (O(ik + log This implies that for
3

---

Exact recovery of sparse binary vectors from generalized linear measurements
LneaseL, when is outside the conjectured hard- ness regime, we do not need the amplitude of y, only the sign information is sufficient to recover the unknown signal.
by k(-). The subgaussian norm of random variable w is denoted by ||w]l
Organization. We present the algorithm and upper bounds in Section 2.1. The information theoretic lower bounds are presented in Section 2.2. In Section 2.3, we present an upper bound for SparseLinearReg based on the maximum likelihood estimator. We also provide a lower bound in this section, which closely matches the upper bound. This lower bounds does not follow the general lower bound theorem for GLMs (Theorem 2.5). It requires a separate analysis based on a conditional version of Fano's inequality. We provide proofs of the upper and lower bound for GLMs (Theorems 2.1 and 2.5) in Section 3. Remaining proofs are delegated to Appendix A. We provide detailed comparison of our results with (Plan et al., 2017) in Appendix B. We conclude with a discussion on open problems in Section 4.
Upper bound (efficient algorithms) (exact recovery)
O ((k + +²) log (n) (Lasso, OMP and this paper)
Upper bound
maX 1 logg( 2.z +1) (this paper)
aN()
(MLE)
corollary to
(exact recovery)
Lower bound
maxie[[:k]]
1 log 1+ 2/2 (2- 1)
aN
(exact recovery)
(this paper
Upper bound
2k n/k log(1+ ++)
(MLE)
(Reevvs et al., 2019))
(approximate recovery)
Lower bound
2k log n/k log(1+ .5) (Reeves et al., 2019))
(approximate recovery)
2. Main results
Table 1. The table gives the upper and lower bounds on the sam- ple complexity sparse linear regression. Note that N(I) :=
2.1. Algorithm
h/2 (+) + (1 - h22 (
where hz()) is the binary entropy
We analyze the simple linear estimation based algorithm from (Plan et al., 2017) for generalized linear measurements, specializing it for binary vectors. The algorithm (Algo- rithm 1) takes the sensing matrix A and the output vector y as the inputs. For each column A A(",, i E [1 n] of the sensing matrix, the algorithm computes 1; = (y, A() Σド= Uj Ag,5 where AJ, is the entry at jHb row and 7th col- umn.
function.
Upper bound (efficient algorithm)
O ( ( 0²) log (n)) (this paper)
Lower bound
k+ log (#)
(this paper) )
Table 2. The table gives the upper and lower bounds on the sample complexity of one hit compressed sensing for exact recovery.
.,) then sorted in decreasing order. The output of the algorithm is a set containing the indices of the top-k elements of the sorted vector. That is, if the sorted vector is (la , lo.............................. la.,) where la, 2 laz for i S j. then the output of the algorithm is S = {ai.... ax}.
The vector = (4......4,)
o ((+ #²) log (m))
Upper bound (efficient algorithm)
(this paper)
Lower bound
2
h + T (this paper) )
log (#)
Algorithm Top-k correlated indices
Input: Sensing matrix A E _ and output y g" Output: a k-sized subset of [1 : n]
Table The table gives the upper and lower bounds on the sample complexity of logistic regression for exact recovery.
1 + (O.....0) 0). 1 E R for each E [1 n] do
1 - ΣØ U3 end for
Notation. We denote the set of integers {1, 2........ n in- terchangeably by [n] and [1 : n]. We will use boldfaced uppercase letters like A for matrices and lowercase letters such as x for vectors. The entry of the matrix at th row and 7th column is denoted by At,. Similarly, the tth en- try of vector is denotes by z;. For any binary vector x = (II,... ......,,,,,, In), we denote the set of indices i where I; = 1 by Sx C [1: n] and we use As, to denote the restriction of A to the columns where x is 1. We use A, to denote th row and (1) to denote :th column. We denote the binary entropy function by hz(+) and differential entropy
Sort I in decreasing order and let S be the top l indices. Return: S
The convergence and sample complexity guarantees for the algorithm shown for the case when each entry of A is chosen iid (O0 1). Note that such matrix satisfies the power constraint in (2). As we argued in Section 1, for the unknown signal x, the output y = Ax + z is correlated with each column A (t) for i E Sx and uncorrelated with A (i) for E Sx. In particular, for large number of samples, when i E
4

---

Exact recovery of sparse binary vectors from generalized linear measurements
Sx, the inner product (y; A ( is close E [y,, A [ = m (for linear regression) with high probability. On the other hand, (y, A ) is close to 0 for j $ Sx. Thus, I, for i E Sx will dominate over l for j & Sx. This line of argument also works when the output is binary, though in this case [ A [00)] for i E Sx is different. This is the main idea of Algorithm I. We first present Theorem 2.1 for generalized linear measurements.
Corollary 2.4 (Sample Complexity of Algo-
rithm 1 for LogisticRegresionn). Algorithm I recov- ers the unknown signal for LogisticRegression if m 2 es (k+5 (log k + log (n k)) for some constant c3.
Comparing the sample complexity bounds of 1bCSbinary and LogisticRegressinn, we notice that the sample complex- ity is similar except that the noise variance o² is replaced by 1/.3.. This relationship is not surprising tionship was also present in the sample complexity bounds in (Hsu & Mazumdar, 2024) (for logistic regression) and (Kuchelmeister & van de Geer, 2024) (for probit model). Note that, in the noiseless case, when 8 - oc (or o for lbCSbinary), the sample complexity is (k log n), which is close the simple counting lower bound of l blog n/k. On the other hand, when 3 = 0 (or - oc for lbCSbinary), m + 0o, which makes intuitive sense as very high levels of noise render the output useless.
Theorem 2.1 (Sample Complexity of Algorithm 1 for GLMS). Suppose the GLM is such that for each i E [m], y: is a subgaussian random variable with subgaussian norm given by llyallar. For any x, suppose for some L,
similar rela-
E [g]( 2 L. lluille, for all i E [m]. Algorithm recovers the unknown signal with high probability if
C
2 min (T,, 1.2] (log (k) + log (n k))
where C' some constant.
To compute the time complexity of the algorithm, notice that the for loop in step takes O(n X m) time and step 4 takes (n log n) time. Thus, the computational complexity of the algorithm is O + n log which is O( + o² log n) for m O((k+ log n. To compute the time complexity of the algorithm, notice that the for loop in step 2 takes Onn x m) time and step 4 takes O(n log n) time. Thus, the computational complexity of the algorithm O(mm + n n). which is O(k + o²)n log n) for m = O(k + o²) logn.
When yj is subgaussian, 3y A,y for any i.j is sub-
exponential random variable. This observation allows us to use a concentration result for sub-exponential random variables to analyse the sample complexity. See Section 3 for a detailed proof".
As corollaries to Theorem 2.1, we obtain the fol- lowing sample complexity bounds for 1bCSbinary and SparseLinearReg. These corollaries are proved in Ap- pendix A.1.
Corollary 2.2 (Sample Complexity of Algorithm 1 for 1bCSbinary). Algorithm 1 recovers the unknown sig- nal for 1bCSbinary with high probability if m 2 ei (k (k)) (log (k) + log (n -
2.2. Lower bounds on sample complexity
We establish lower bound for generalized linear measure- ments using standard information-theoree arguments based Fano's inequality. While the upper bound in Theorem 2.1 is derived for the maximum probability of error over all k- sparse vectors, the lower bound applies even in the weaker setting of the average probability of error, where x is chosen uniformly at random.
k)) k)).foo for some constant e1. Corollary 2.3 (Sample Complexity of Algo- rithm 1 for SparseLinearReg). Algorithm I recov- ers the unknown signal for SparseLinearReg if m 2 c2 o2) (log (k) + log (n (ok-k) k)) for some constant C2-
Theorem 2.5 (Lower bound for GLMs). Consider any sens- ing matrix A. For uniformly chosen k-sparse vector x, an algorithum & satisfies
Interestingly, the sample complexity for both 1bCSbinary and SparseLinearRRg is the same. This can be explained by similar values of L., which result in similar rates of concentration of 4 around their expectation in both the cases. This also implies that in the regime where m = O(kk + +22 log(n- - k)),, having access to A? x 2; instead of sign(Af x does not improve the sample complexity beyond constants.
IP (o(AA)) xx) 2 only if the number of measurements
klo (2) (1 (1- h2( + 8k log
m
As klog n//k:
for some such that I Z 18yi x|A), i [m]] In particular, when y E (-,, we have E (g(AT 2 1 (1,, x|A) where the expectation is over the randomness of A and x.
Using Theorem 2. we obtain the following corollary for logistic regression (see proof in Appendix A.
'The current form of Theorem 2.1 is stated for sensing matrix A where each entry is chosen iid (0, 1). However, the proof technique can easily generalized for other distributions.
The lower bound can be interpreted in terms of a commu- nication problem, where the input message x is encoded to
5

---

Exact recovery of sparse binary vectors from generalized lincar measurements
Ax. The decoding function takes in input the encoding map A and the output vector y in order recover with high probability. For optimal recovery, one needs at least message entropy number of measurements (follows from noisy capacity
Theorem 2.5 also implies an information theoretic lower bound for SparseLinearReg. which is presented below and proved in Appendix A.2. Note that the denominator term in the bound log (1 +1+ 2+) is the capacity of a Gaussian channel with power constraint and noise variance o².
channel coding theorem (Cover& & Thomas, 2006)). In Theo- rem 2.5, the entropy of the message set log (x) Rd k log
Corollary 2.8 (SparseLinearReg lower bound). Under the average power constraint (2) on A, for a uniformly chosen k-sparse vector x. an algorithm & satisfies
and the proxy for capacity is the upper bound on mutual information I. We provide a detailed proof of the theorem in Section
TP (()(A,)) x 5
We first present lower bounds for 1bCSbinary and LogisticRegression. The lower bound for lbCSbinary is given for any sensing matrix A which satisfies the power constraint given by (2), whereas the one for LogisticRegression only for the special case when each en- try of the sensing matrix is iid ("00, 1). Recall that (2) holds in this case. For 1bCSbinary (and LogisticRegression re- spectively), we can use the upper bound of IE [((AA"")) x 21 on the mutual information term. The dependence of o² (and 1/33² respectively) requires careful bounding of this term, which is done in the formal proof' in Appendix A.2.
only if the number of measurements
2 klog (x) - (I2(6) + logg)
1 log (1 +++ +
2.3. Tighter upper and lower bounds for SparseLinearReg
We present information theoretic upper and lower bounds for SparseLinearReg in this section. Similar to Section 2.1, our upper bound is for the maximum probability of error, while the lower bounds hold even for the weaker criterion of average probability of error.
As mentioned earlier, we need least k log (n/k) mea- surements for 1bCSbinaryand LogisticRegressinn. This is because the entropy of a randomly chosen k-sparse vector is approximately l log ln/k) and we learn at most one bit with each measurement. However, due to corruption with noise, we learn less than a bit of information about the unknown signal with each measurement. The information gain gets worse as the noise level increases. Our lower bounds make this reasoning explicit.
We first present an upper bound based on the maximum likelihood estimator (MLE) where we decode to & if, on output y.
* arg max p(y[x)
xE(0,13
[x x
Corollary 2.6 (1bCSbinary lower bound). Suppose, each row A,, i E [1 : m] of the sensing matrix A satisfies the power constraint (2). For a uniformly chosen k-sparse vector algorithm satisfies
where p(y[x) denotes the probability density function of y input
Theorem 2.9 (MLE upper bound for SparseLinearReg).
Suppose entries of the measurement matrix A are i.dd (O, 1). The MLE is correct with high probability if
P ((((A))) xx) 58
for the problem of lbCSbinary only if the number of mea- surements
n.((1)
m 2 max [E(1:k] 2 log ( 2 + 1)
(8)
m
1: + >
02
log
72 (1- h8) + 8k log n k loggg/k n/k
where N(I) = à h2 (t) +
h22 (1112)
2
K
Corollary 2.7 (LogisticRegression lower bound). Consider a Gaussian sensing matrix A where each entry is chosen idd (O, 1). For a uniformly chosen k-sparse vector x, an algorithm & satisfies
We prove the theorem in Appendix A.3. The main proof idea involves analysing the probability that the output the MLE is 2/ Hamming distance away from the unknown signal for different values of I E [1 k] (assuming k S n/2). This depends on the number of such vectors (approximately 20) and the probability that the MLE outputs a vector which is 2/ Hamming distance away from x.
((((A, x 8
for the problem of LogisticRegressonn only if the number of measurements
Note that when = k (1 k). nN(() = nhz(k/n) x
I log a and log I 2 log n/k (see the bound for Corollary 2.8). log k +1)
(R(1-
2 + +1) < log ( + 1). Thus,
1
1
12 (1 k
h2( + 5k log
m 2 2
k
log
m is at least
82
A log n/k
6

---

Exact recovery of sparse binary vectors from generalized linear measurements
(W1....> Umm) Consider the event
9220
ml
m Σ
F
yr
y. for all j E S,j' e so
9200
It is clear that under F, the algorithm is correct. We will compute the probability of F
2050
m
m
}
P IP
Σ
Yi ye Σ
Vi
ViAis
3000
20000
35000
JESS'ES"
m Σ Yi
Figure 1. The figure shows the plot of the MLE upper bound (8) (given by ml) for different values of k. This is displayed in blue color. A plot of (1) is also presented for = k (1 - )
Σ Σ
PP
Σ ViA
JES SEES
1=1
log 20 +2)
in orange color, given by m2. A part of the plot is zoomed in to emphasize the closeness between the lines. In these plots, o² is set to I, n is 50000 and & ranges from 1000 to 25000 (n/2).
Σ
TP
Σ (vi(As. - As.s)) 2
JES JES
J'ES
(10)
It is not immediately clear if this value of 1 k (1 *) is the optimizer. However, for large n, this appears to be the case numerically as shown in Plot 1.
For any i [1 ml. j E S and j' E 8 we first compute
E La (Ai. )..
E [Bi - Ai.
= E [yi. Ai,5) - E [viAi
Inspired by the MLE analysis, we derive a lower bound with the same structure as (8). We generate the unknown signal x using the following distribution: A vector x is chosen uniformly at random from the set of all k-sparse vectors. Given x. the unknown input signal x is chosen uniformly from the set of all k-sparse vector which are at Hamming distance 21 from x. The lower bound is then obtained by computing upper and lower bounds on (A. y; x(x). We show this lower bound only for random matrices where each entry is chosen iid (O, 1).
(a)
[y: Ai,]
(11)
(6)
[r,
k
E [v:AA x
k
E A E [
k
E [AT xg (ATx)]
Theorem 2.10 SppareLLineaRRee lower bound). If each en- try of A is chosen iid (0, 1), then for a uniformly chosen k-sparse vector x, an algorithm & satisfies
( E [g' (Afx)) = E (12)
where (a) follows from the fact that yi and AL, are zero mean, independent random variables and (b) follows by defining Ai, = Ejes Ar, and noticing that the random variables Yt are identically distributed for all j E S, (c) follows from (6) and (d) follows from Stein's 's lemma.
( (x)))*x))))) 58
only if the number of measurements
nl(()) 2log n - h2((6) 8k log
m max [E[1sk]
1/2 log (1 2/2 (2 ())
P
(2) (Ai. Ai.))) 20)
The proof of Theorem 2.10 is given in Appendix A.3.
IP
(yn (Ai. -)a S
If we choose / 1 (1 11-4 +) in Theorem 2.10, we recover corollary 2.8 for the special case of Gaussian design.
PP
(3n - -Ary)) mm < -mm
3. Proofs
$ P
(ui(Ar.) - Ac..)) mE
mm 2 mE
Proof of Theorem 2.1. Consider any input x and a sensing
matrix A where each entry is chosen iid N 1). Suppose x supported on S C n] where |S] = k. Let y =
7

---

Exact recovery of sparse binary vectors from generalized linear measurements
To compute this, note that for all E [1 : ml] yy is a subgaus- sian random variable and yi (Ai.j Az,²)) being product of
where (a) holds because A and x are independent. Let
Uj denote (U1.-..,,i--.
two subgaussian random variables is subexponential ran-
dom variable (see (Vershynin, 2018, Lemma 2.7.7)). Note that E.
m
1(y:x Σ [yxx|A HeE(::--1)
>>=n i=1 (Ua - A1ge))] = mF where E was de- fined in (12). Also,
HVviAA ())(1:--))
11ve (Ais Arg)) - Blly
(0)
C llve (Ais - Ai.s) )1
H( |x, A, ()E(L)-1))
(a)
11Belle22 |I(Ar. - Av, ) 11pb
(H())A)) ((AAA))H(y(ixAAA (v(
(0) C 11billes2 20"
= Ci | 1ellles
for some constant C1-
Here, (a) follows from (Vershynin, 2018, Exercise 2.7.10), (b) from (Vershynin, 2018, Lemma 2.7.7) and (c) from (Vershynin, 2018, Example 2.5.8). With this
ml
(14)
where (a) follows from H A, V) S (())A)
and Hy: A, U)e(tsi- ( Xx A) as y is condi- tionally independent of U)ε[1:i-1] conditioned on and A and (b) follows from the assumption in the Theorem. Thus, from (13) and (14),
P
(wi(Ars Ai.)) - mF 2 mF
(a)
m² m² L²
mE
S 2 eex
-cmin
mCf 1uille
On llvallea
ml 2 A log (n/k) (1 h2(0) + 5k log (n)
t: n/gg
(b)
mmL C7
mL
2 exx
(-em cm min
G
This gives us the desired bound.
We can further simplify I(ys: A|) when yss E (-1,1),
where (a) follows from (Vershynin, 2018, Theorem 2.8.1) and (b) follows from the assumption in the lemma that
X|) = H A) - H()s(x A)
Eig xAT 2 L. Thus, from (10),
E
Mell
lulllaz
(a) < 1- H(y(xx
P (FF) S k(n e)pexp (-02m min min L))
where (a) holds because H(yalA) S H(y:) and V/1 is conditionally independent of conditioned on A,
+ Of m 2 C2 (log k + log - k)) min (L? L)
(Ai..., Ai- Ait1,..., and x. Here A, i E [1: ml] denotes the 8hh row of the sensing matrix A.
for some constant C2.
Proof of Theorem 2.5. Suppose x is distributed uniformly on the set of all k-sparse binary vectors. Then,
Suppose x is fixed and IP (1; = 1) = 1/2 + for some [11/2 Then [ys A.] 21 = (={(A"))
y; = Hxx) - y)
H(y A x)
(a)
E
h2
+
t
2
(a)
~ log hō) ô log
-1)
k
Fx
EA
4
+ 1)
2 1-- 1)
1
) [x
2
k n/k hz( 5k log (n)
(13)
= 1 - Ex
E
(21)² x
where (a) follows from Fano's inequality (Cover Thomas, 2006, Theorem 1). We also note that
(o(AFx)) x)) ? [x]
1 - Ex
E
I(A, x) = x(A;x) + x(y;
= 1 EA,
[(o(ATx))]]
[]]
(a) 0+ AA):
where in (a), the expectation over A and The inequality
8

---

Exact recovery of sparse binary vectors from generalized linear measurements
(b) follows from (Topsøe, 2001, Theorem 1.2)*. With this [|)x E [o(A
ences and Systems, CISS 2008, Princeton, NJ, USA, 19-21 March 2008, pp. 16-21, 2008
Candès, J., Romberg, J., and Tao, T. Robust uncertainty principles: Exact signal reconstruction from highly in- complete frequency information. IEEE Transactions information theory, 52(2):489-505 2006.
4. Conclusion and open problems
We analyze simple algorithm (the "average algorithm" from (Plan et al., 2017) followed by 'top-k" selection) for recovering sparse binary vectors from generalized linear measurements; along with an information theoretic lower bound. This gives optimal sample complexity characteriza- tion for IbCSbinary and LogisticRegression hand, the required number of measurements for the noisy linear case (SparseLinearReg)) which is ((k af) log n), is as good the sample complexity of any other known efficient algorithm for this problem, up to constants. An interesting open problem is to find a design matrix and an efficient algorithm which requires less than (I + o²) log n samples for SparseLinearReg When the noise variance is zero, we show such an algorithm in Remark 1.1.
Cover, T. and Thomas, J. Elements of information theory. Wiley-Interscience, 2006.
the other
Do Ba, K., Indyk, P., Price, E.,, and Woodruff, D. P. Lower bounds for sparse recovery. In Proceedings of the Twenty- First Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA '10, pp. 1190-1197, USA, 2010. So- ciety for Industrial and Applied Mathematics. ISBN 9780898716986,
Donoho, D. L. Compressed sensing. IEEE Transactions on information theory, 52(4): 2006.
We also present almost matching information theoretic up- per and lower bounds for SparseLinearRes given by (8) and (9) respectively. The bounds are in the form of an optimiza- tion problem. While we present numerical evidence which suggests that (8) is optimized by / = &o proof still missing. The bounds in (8) and (9) also differ slightly by constants the denominator, which seems to be persistent gap in this problem.
Gamarnik, D. and Zadik, I. High dimensional regression with binary coefficients. estimating squared eπror and a phase transtition. Conference on Learning Theory, pp. 948-953. PMLR, 2017a.
)) a formal
Gamarnik, D. and Zadik, I. Sparse high nigh-dimensional lin- ear regression, algorithmic barriers and local search algorithm. arXiv preprint arXiv:1711.04999 2017b.
Gamarnik, D. and Zadik, Sparse high-dimensional linear regression, estimating squared error and phase transition. The Annals of Statistics, 50(2):880-903, 2022.
Acknowledgment This work is supported in part by NSF awards 2217055 and 21 12665. The authors would like to thank Krishna Narayanan who introduced them to the binary linear regression problem at the Simons Institute program on Error-corrccting codes.
Hsu, D. and Mazumdar, A. On the sample complexity of parameter estimation in logistic regression with normal design. In The Thirty Seventh Annual Conference Learning Theory, pp. 2437.2437. PMLR, 2024.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Jacques, L.,, Laska, J. N., Boufounos, P. T., and Baraniuk, R. G. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE transactions on information theory, 5944):2082-2102, 2013.
References
Kakade, S. M., Kanade, V., Shamir, O., and Kalai, A. E ficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.
Acharya, J., Bhattacharyya, A., and Kamath, P. Improved bounds for universal one-bit compressive sensing. 2017 IEEE International Symposium on Information The- ory (ISIT), pp. pp. 2353-2357. IEEE, 2017.
Kuchelmeister, F. and van de Geer, S. Finite sample rates for logistic regression with small noise or few samples. Sankhya A, pp. 1-70, 2024.
Boufounos, P. and Baraniuk, R. G. 1-bit compressive sens- ing. In 42nd Annual Conference Information Sci-
Liu, W. Gong, D., and Xu, Z. One-bit compressed sensing by greedy algorithmss Numerical Mathematics: Theory, Methods and Applications, 9(2):169-184 2016.
'Note that, unlike (Topsøe, 2001), entropy and mutual informa- tion are defined with logarithm to the base

---

Exact recovery of sparse binary vectors from generalized linear measurements
Matsumoto, N. and Mazumdar, A. Binary iterative hard thresholding converges with optimal number of measure- ments for 1-bit compressed sensing. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 813-822. IEFE, 2022.
Matsumoto, N. and Mazumdar, A. Robust 1-bit compressed sensing with iterative hard thresholding. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2941-2979. SIAM, 2024.
Mazumdar, A. and Pal, S. Support recovery in universal one- bit compressed sensing. In 13th Innovations in Theoreti- cal Computer Science Conference (ITCS 2022). Schloss- Dagstuhl-Leibniz Zentrum für Informatik, 2022.
McCullagh, Generalized linear models. Routledge, 2019.
Ndaoud, M. and Tsybakov, A. B. Optimal variable selection and adaptive noisy compressed sensing. IEEE Transac- tions on Information Theory, 66(4):251772532, 2020.
Plan, Y., Vershynin, R., and Yudovina, E. High- dineessimnii estimation with geometric constraints. Information and Inference: Journal of the IMA, 6(1):1-40, 2017.
Reeves, G., Xu, J., and Zadik, I. The all-or-nothing phe- nomenon in sparse linear regression. In Conference on Learning Theory, pp. 2652-2663. PMLR, 2019.
Servedio, R. A. On pac learning using winnow, perceptron, and a perceptron-like algorithm. In Proceedings of the Twelfth Anmual Conference on Computational learning theory, pp. 296-307, 1999.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-28) 1996.
Topsøe, Bounds for entropy and divergence for distribu- tions two-element set. Ineq. Pure Appl. Math, 2
(2), 2001.
Tropp, A. and Gilbert, A. C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions information theory, 33(1)):4655-4666 2007.
Vershynin, R. High-dimenssonad probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018.
Wainwright, M. J. Sharp thresholds for high-dimensional and noisy sparsity recovery using l1-constrained quadratic programming (lasso). IEEE transactions on information theory, 25(5):2183-2202, 2009.
10

---

Exact recovery of sparse binary vectors from generalized linear measurements
A. Proofs
A.1. Missing proofs from Section 2.1
Proof of Corollary 2.2. We need to compute lower bound T. on [A]' Instead of computing IE []'(AA")]] we will 1l
compute E [t,] for any j in the support of From (11) and (12), we note that E [B,. E [g'(AA x)] Also note that E [t,l E 1 [ys Ai,ll-
For any U C [1 nl.. we denote ElEu Ar, by A:2 For any Aig = a,
(y 1|A a)
P (Ar,))(1) + 2 -a)
(1,5((1) +
0
Vk: 1 + -k=1+022
Vk - 1 02
(- /k 11+2
a
1 12
where ((x)
2x 1-o0 d is the cumulative distribution function of the standard Gaussian distribution. Thus,
(y: = - = a) = (- and
E [usi Ai.5 a] = 1- 24 (-
Vk 1
We are ready compute E [A,, [M AI.
[A E 1y |A,,ll
Ar.i
Ai.j 1-20 2Φ
Vk 1 1 0Z
A
E [A
2TE
A $
V/ + 02
Aij
2E
Aig
(15)
Vk
1 1+o
A
A
Vk - 1+ Oz
a 2m
1
Vk 11
4 dt
da
V
Vk-1407
dE - e
do
2m
-00
1
0
1vo-1+o"
2 2 aC Te E
7 da dt
2T
1y 1+
1
2
2 e- dd
da
2T
1
00
Pek 1103)
e I dl
2T
+ 211
c
dt
2T
(k + +2)
000 V2T
(16)
2T +2)

---

Exact recovery of sparse binary vectors from generalized linear measurements
where (a) follows for change of variable formula for integration. From (15) and (16), we have
2 V π
(17)
v(k (k+ 02))
From (Vershynin, 2018, Example 2.5.8), we also note that l1 1. Thus, L = / & V(k+o²)
and min (2, L3
which when substituted in (7) gives the desired bound.
Proof of Corollary 2.3. We first note that x[) Ely.Auol for any j in the support of x. This follows from Taas
(11) and (12). We first compute I Aigl. which is the same as IE [[A]x x =:) Aij] for SparseL.iearreeg Note that E [ATx 2)) (At,)) E [4,,] 1. Also, from (Vershynin, 2018, Example 2.5.8)
SCUk+o
for some constants C. With this,
1 == L. CVK + o2
1 g/z
Note that min [3} L2, which when substituted in (7) gives the desired bound.
Proof of Corollary 2.4. We will first compute g( g(ATx) E [M for LogisticRegression.
= L [
-AAx
1
1 1 8AIx
1+e
AAT
BAAX
(a) tanh
[BATx
2
where (a) uses the definition of tanh. Then
E
(A x)]
2
cosh 2
9AAx x
(0)
3 E
(onTx)²
where (c) follows from the inequality cosh(t) S e (see (Vershynin, 2018, Exercise 2.2.3)).
(sA?"*)"
Now, we need to compute E
where Afx N(O, k). Let = Then
12

---

Exact recovery of sparse binary vectors from generalized linear measurements
E
14 -d² 12k2
da
2
01
1200 da
k
/2TTT1
V k
2
(18)
V
+ 52k
Thus,
8
E {
2
2
2 B2k
1
2
2/
2/ k
From (Vershynin, 2018, Example 2.5.8), we also note that 1ellla = 1. Thus, L, = which gives the desired bound.
//
2 2/32+4
and min (L, 1,3) = =12,
A.2. Missing proofs from Section 2.2
Proof of Corollary 2.6. Consider a sensing matrix A which satisfies the power constraint (2).
Here A E [1 m] denotes the 1th row of the sensing matrix A. Let Q(+) be the Gaussian Q function. For any realization
bE R of A7'x,
F(y; 1|Axx x b) P(2 2 -b) =
sign(b)
+ Q (61)
2
For 1e R(a)= = 1 S0 e u22 Then Q(a) -R(a). Suppose is fixed. Then,
V2H
[my]AA] =
=
E [y x]
1 sign( (ATx) x)
(A7x))
- (1- 11- (1-11- sigsinn(A
2 + sign (AT)( (AA x
+ sign(A?
2
[Axx
sign(A, x)
1-2Q
|AAx]
(igg(AAxx
2R
For any a > 0,
(a)
1
-u 12
2
1
<
1du
2
2m
13

---

Exact recovery of sparse binary vectors from generalized linear measurements
Thus,
|AXx| x
27
[
E
=E
2R
Af x v 2TT
E
(a)
2h
TT?
where (a) follows from the power constraint sparse vector. Thus,
(A) 27
(see (2)). This holds for any x, including a randomly chosen
m 2 To²
(1- h2(()) + 8k log (n) h log n/k 2 0² log (n/k) (1 h2(6) + òk log (n) ke logg//
k log (n/k)
2k
(19)
On the other hand, [()xx|A) 1. Thus,
l: log (n/k) (1- (8) + 8k: log (n)
k log n
m [y):x|A) S Σ H()AA)
S m.
(20)
Combining (19) and (20), get the desired bound.
Proof of Corollary 2.7. Consider Gaussian sensing matrix A. Suppose x is distributed uniformly on the set of all k-sparse binary vectors.
Suppose tanh SA.x x
(1-e (1-e-9A(x
Then,
2(1ee-0A?y
1 + and
1 1+e-DA7x
14e - -AAx 2 -
With this,
E (A{x)))
E [
tann 3ATx 27
EE'
Note that,
BATx
27
3ATxx
27
tanh
sech
2
2
14

---

Exact recovery of sparse binary vectors from generalized linear measurements
and
3A
x
27
E
sech
=E
2
cosh
x
(n)
[2A[x/22 "
2
(
1
B2//2
(c)
B2h
2
1
2
where (a) follows from the inequality cosh(t) S e2/2 (see (Vershynin, 2018, Exercise 2.2.3)), (b) follows from (18) and (c)
holds because 1 2 S vI+z
for any 2 0. Thus,
E [ 1
8²k 2
This implies that
B²k m
(1- h2((8) + 8k log (n) k log n//k
2 k log (n/k)
2
Thus,
2
1 h2(6) 5k log (n)
m 2
log (n/k)
8²
k llog n/k
1
ha (0) 8k log (n)
log (n/k)
(21)
82
k log n/k
We also know that for any i, A
H (3 A) I 1. Thus, we also obtain that
m 2 k log (n/k) (1- h2(6) + 8k log (n) k blogn/k n/k:
(22)
Combining (21) and (22), we get the desired bound.
Proof of Corollary 2.8. Suppose is generated uniformly at random from the set of all k-sparse vectors and A is any sensing matrix which satisfies the power constraint given by (2). Then,
x(): h(valA) A()lx, A)
(b(wx)) 1(AA x + xx(x,A))
h(() 1((=z)
S (h(ws)) -h(z:))
where in the last inequality, w, ~ N 0Z) where Var(v:) S o We will now compute upper bound on Var(y:).
Var(y:) < E (AT 2; EE [AA)))]] +o²
< k + 00
Thus, we have
1
log 02 +1.
k:
(h(w;) - h((z))
(23)
2
15

---

Exact recovery of sparse binary vectors from generalized linear measurements
With this, conclude that
2k log x
8k log n
m 2
loo (+t4 + 1)
A.3. Missing proofs from Section 2.3
Proof of Theorem 2.9. We consider sensing matrix A where each entry is chosen iid (0, 1). let Xr denote the of all k-sparse binary vectors. That is & fx' {0, 1)" | k). We decode to x if, on output y,
arg max p(y(x') x'e
where p(yixt x') is the probability density function of y input x'. We assume that k S n/2. Suppose unknown signal is x. The eπror event & is
E {y: 3x * such that p(y/ > p(y\x)}
Then
P(E)
Σ Σ p(ply|))>p(3 t=1 RE
dx(xx))=2
and x has support on U [1 n), (1] k. Then, conditioned on x. Vr generated from Eies Ar, which denote by Ar,s That is, Ur A,,s 2, where A,,s ~ NNO,, k). Similarly, conditioned on ス, Yr A, + 2, for Ar, = Eieu Ar, where A,u NN0 k)). For any 1 E [1 R], computing P (p(y|x) > p(y(x)), we have
Suppose x has support on S [1
|S| [8|
F(y(y|x) p(y|x))
log p(y|)t)
>0
p(y(x)
m
plut (
log
=0)
plyr plur|Ar,s) Ar.s)
m
(ur Arre)
2
(yr
Ar,s)
> >0)
202
202
m
(Ar Ar,s)
m
(Ar + Ar.))
(Aru Ar.s)
2
16

---

Exact recovery of sparse binary vectors from generalized linear measurements
(or Anv)
where in (a), we used the Gaussian density formula which states that for any and V. p(y. (Ar,v) = V2no= Using the fact that yr = Sr, Ar.snu + Zr, we have
20
P ((p(y(2) > p(y|x))
m
P
Σ
(Anun - Ans + Ar + 2r) >
m
A,,i, + Ar,syu + 2Ayuns)
(Aruns A,,su)
P
(Anun An,ovu)en)
r=1
APans
A Arrsr
AransAnsu + +..ssw)
2
2
1=1
P
(Aruss - Ar,)(()))) >
- E -A,s)))A,,)11)) A
2
r (Arus - Ar,svu)zz
P
(Arans Ar.s)e) 20
m
(Aruus - Ar,siu)
20
Let = AAuns - Ansuu Note that b, ~ 20, Let b- = (bi,...,bu Let e = =(e1,...,e.. denote the realization
of b. Then,
Σ (Arus - Ansyu)zz
P
Cranl (Aruns - Ar.s()) 0
v Em (Armss Ar.suu)
20
Σ Em- (b,)²
m
b
P
)>
(br)²a
20
(0)
/ pb(e))
Σ 2r
m
Em= (er)
de
Dm (c
20
= =f =fma(o)
v >mm
(
de
2a
17

---

Exact recovery of sparse binary vectors from generalized linear measurements
where in (a), (e) denotes the density of b and de shorthand for deidez- ... dem. To analyse this further, we the upper bound Q(x) S _
12 =2
m V
(e,)
J po(e)2
de
20
/ (2TT 21)mm/²
or
2
21
2
80
de
m2
/
2(
20 (
00 ))
de
(2T 21)Tn/²
m//
(21)m/2
m/2
2( 2
Σm
(2( de
+
(2T) (2T)m//
21
80
m/2
20²
2( 7. log(1+ 21)22))))
Next, we observe that
Xx' E No. dx(xxx') = 21H1 = (k) (n. (2)) -)
kha (n)
(*taaaa (n=i) hos (m-
= 2
where (a) uses the incquality (w) < 2m/2(k//)) ((Cover & Thomas, 2006, Theorem 11.1.3)). Then,
P(E) S 2nN(112 lon( (1+ 2422))
2nN(1)
if 2 max log (1 + 20²
Proof of Theorem 20. We consider a joint distribution given by the following process. X is generated uniformly at random from the set of all k-sparse vectors. Given &, the unknown signal x is chosen uniformly at random from the set all vectors which are Hamming distance 2/ from for some [1 : k] (assuming n//2). We will denote the realization of by and the realization of by &. With this, given & x,
P(x x
(77
Note that the marginal distribution of x is uniform over the set of all k-sparse vectors.
We will be using the below set of equations in our further analysis. For x (æı,..., any j.1 E Sx where j # 1, we
18

---

Exact recovery of sparse binary vectors from generalized linear measurements
have
P( 1|x = x) (T7))
k-1
and
(24)
(9) ("7 k
P (z)= x = 1| = x)= = (k73) (MTh) (MTT))
-(xx)
1-1
k:
-
(25)
(a7T)
k
h-
For any sensing matrix A, output vector y and an unknown signal x generated from X using the above process, we have
(x H ( X,)
2 H(x - H))
(0)
2 H(x[)) h22 8log
n
kk)
Σ = H( = x) - (6) (((
- -llog
n2
k:
Σ (x = x) log (1) (MTTA) R) h2((8) - 88 log n
k)
(0)
kh2 k
+ (n ki)12
log (k + 1)
log (n k + 1) - h2 (0) 5k log
nl log n h2( 5k log n
(26)
where (a) follows from (Cover& & Thomas, 2006, Theorem 2.10.1), (b) follows from (*) S n² (c) follows from 1 n+1 (2hn((k/m)) ((Cover& & Thomas, 2006, Theorem 11.1.3)) where h2 the binary entropy function and (d) follows by
defining (() $ h2 (t) + (1 - Ma2 (
Next, we will compute an upper bound on
1 (A,,): = (AA + (y;
(0) 0 + ((;
Σ [ 0jE(1ai1]]
where (a) follows because A independent of both x and x. particular, A is conditionally independent of x conditioned on &. Here, (b) follows from chain rule for mutual information where y)E[1:i-1] denotes (y1, -ul.-..,Vi-1)
Suppose h(-) denotes the differential entropy of continuous random variable. For any i E [1 : m)]
(y x|A, Bje[1xr-1], x)
A 1) x) h(y//x, A, 1)
(a) h(vil Ac.ESE x) - M(ATx x + Y,
A(yj:Ar.,ES...)) x) h(2z)
h( x) 1 log (2iTe0
where in (a), we use Ai,eSSa to denote the set of elements A.,, for E Sx. Conditioned on x and Ai,jeS; =ai,eSS
19

---

Exact recovery of sparse binary vectors from generalized linear measurements
h/// = A.J.s a(.EEs))
(a) U/ -B X, Ax = =a.jesa x= x= = -a.jesx)
h(Wn: ((Wa.scs.)
where (a) follows by noting that differential entropy does change by centering ((Cover & Thomas, 2006, Theorem 8.6.3)) and (b) follows for W N (0, o where o Var( - E [u/ & = A.jss a.jess] X x, A i.jEs = at,)sss) from the fact that for the same variance Gaussian random variable maximizes the differential entropy and it increasing with increasing variance (CCover Thomas, 2006, Theorem 8.6.5 and Example 8.1.2))
Recall that each entry of A is chosen iid (0, 1). In that case, Var (wi [yi X, Aijesz a..jsss)) conditioned on
X and Ax aijes is given by EE (y:) 2 | X, Aijes= aijjESx - (E Wy X X, AijeSz aisesz)) We first analyse the first term.
E
(ys) & x, Ai,jes= -ai,EE83
E
E
(ATx 1=======> &, ArsES = JIJES,
For any x x,
E [A x + 2;) x, a.jes, x
1+ (a,,Senss)) ?
where (a) holds because conditioned on A aijes; and x x, the random variable A7'+2; = A and |Sx Sxl L.
+ars,ns +2
Similarly, analyze the second term.
E [y X = x, Aijes = ai.jess
E A x + 2//x x, A1,ES a(.jEs)
= E E A x + 24 x= ANJES = aI,ES,,
For any x x,
E [ATxx + 2/8= X, Aijes: -ii.jes, x
and
E EA + 2/x= X, AijeSa = a.jjESs x|] = E E aiss,ns 1 = X, Aijess = x]]
(a) k ai
where (a) follows from (24).
(E [y = &, Ai,jes, =aijes2))
k 11 2
Σ
af. + Σ
aigail
JESx
31l88
j
20

---

Exact recovery of sparse binary vectors from generalized linear measurements
On the other hand,
E (wi) 2 { = x, Ax = a1.s
Ex 1 -² + (as,)&n(s2) )²]
k-1
k-2
@ 1+ 0² +
k-1-22
+
aiyGil
k
JESx
= =1 + k-1 Σ
1-1
k (
aid +2
Σ
k
k
k-
JESx
SJCS& jf
where (a) follows from (24) and (25). Thus,
Var yf - E 11:188 = X, AiJes= = -a,jEssa
X =xx, Aijess = =aijess)
h 1-1
k k-1-1 k
h 1-1²² 2
=1+ 0² + h
Σ
o +2
Σ
01.0 -
Σ
o +
Σ
an
- 1
k
jESz
SK j+
jESz
3.C33 j
k
k k-1
- 2² +
4 -
Σ
ai.j
k
k
k (k= - 1)
JESx
1188%
1+1
Thus,
AI.ES, = / (A(aa)(vllx= = A.JES = =a.jESx)da
f PA (a) | log
1
2Te 1+02+ +
((==)
k-1
2 k-1
Σ
asgasi
da
k
K k
k( 1)
jESx
5.155
j&l
(0) 1 log
2
1+02+ +
(
k-1
Σ
2
k -
Σ
aigata
da
2
Te
1
1o (k:
1)
JESx
(b) log
2Te
12 ((xx) k
o2
(K-1))
1)
2
where (a) follows from Jensen's inequality and (b) follows by noting that E [A]]]] = 1 and E (Ar.AA. 0 for any and j. I, where j # I and x is k-sparse.
Thus,
m [yxx A, 11, S m
1
((+T1))) )))
log 2TE
[+022 0² +
log (2TTe²*)
k
2
= m
1)
log
+ σ² k
2
2
Using this and (26), conclude that
nN(I) 2 log n h2(6) 8k log
m 2
//2 log (1 + 1 z (2 1
21

---

Exact recovery of sparse binary vectors from generalized linear measurements
B. Comparison with (Plan et al., 2017)
Algorithm is similar to the two step estimation procedure outlined in (Plan et al., 2017) which was given to estimate the the same as the first step of the procedure in (Plan et al., 2017, Section 1.2) where linear estimator is computed. The second step our algorithm (sorting and keeping the top-k indices) be thought of as projection a feasible set (Plan al., 2017, Section 1.3). However, this requires the estimation error to be small enough for the exact recovery of binary vector.
unknown signal within two norm guarantee. Computing the vector (4..... (n)
The setup in (Plan et al., 2017) is for the recovery of an unknown signal with small two-norm error, whereas our problem of exact recovery of a sparse binary vector is more suited for recovery under infinity norm. This results weak bounds (m =
O(k2)) when we specialize various results (Plan et al., 2017) to our case. We first note that we require [
for exact recovery. Otherwise, there exist two binary k-sparse vectors which have hamming distance at least two.
We first consider the 1-bit compressed sensing result in Section 3.5 (page 13). Setting the LHS to / / we get
2
2
k log (2n/k)
c
This implies that m x C₁ log (2n/k) for some constant C1-
Next, we consider (Plan et al., 2017, Theorem 9.1). Note that for 1-bit compressed sensing 1/² 1 and
# = E s1 (a1, ø)
|s
x)]
1
2
k
k
π
v (k + 0²)
2
Vi
π
v(k 02)
where (a) follows from (17). Then,
vk k
r
| p
X
V(k
g2)
Vk
Vk + 02)
We require || - pøl12
/=²)+ in order to exactly recover the unknown signal x.
We assume that K is also closed cone in R". Then, by (Plan et al., 2017, Section 2.4), wr(K) twi (K) < tC / loo (2n/k) ((Paan et al., 2017, Section 2.4)). We choose = w1 (K). Substituting the bound for LHS and taking the limit t. + 0, we get
2 V (k + 2
80 k log (2n/k)
v m
Thus, R8 40 + o²)k log (2n/k).
22


Reviews:
[{"review_id": "wn8EsxH2o3", "reviewer": "Reviewer_g4Gp", "summary": "This paper addresses the problem of recovering a $k$-sparse binary vector from generalized linear measurements. Given observations $y = (y_1, \\dots, y_m)$, which are related to a sparse vector $x$ through an inverse link function $g$ such that:\n\n$$\n\\mathbb{E}[y_i | A_i] = g(A_i^T x), \\quad \\text{for each } i \\in [m],\n$$\n\nthe goal is to accurately reconstruct $x$. Since $x$ is binary, the problem reduces to support recovery.\n\nIt presents a simple “linear estimation followed by top‑k selection” algorithm – essentially a one‐shot version of an iterative greedy scheme – and provides tight sample complexity guarantees for several settings, including noisy one‑bit compressed sensing (1bCSbinary), sparse linear regression (SparseLinearReg), and logistic regression. In addition to the algorithmic upper bounds, the paper offers nearly matching information theoretic lower bounds. Notably, logistic regression and 1-bit compressed sensing emerge as special cases of this framework. \n\nThe authors build upon the simple linear estimation algorithm from Plan et al. (2017), focusing on its application to binary vectors. They establish both upper and lower bounds on the sample complexity required for successful recovery:\n\n## Upper Bound: Sample Complexity of Algorithm 1 (Theorem 2.1)\n\nIf the generalized linear model (GLM) ensures that each $y_i$ is a subgaussian random variable with norm $\\|y_i\\|_{\\psi_2}$, and for some $L$,\n\n$$\n\\mathbb{E} \\, g'(A_i^T x) \\geq L \\cdot \\|y_i\\|_{\\psi_2} \\quad \\text{for all } i \\in [m],\n$$\n\nthen Algorithm 1 successfully recovers $x$ with high probability, provided the number of measurements satisfies:\n\n$$\nm \\geq C \\frac{\\log(k) + \\log(n-k)}{\\min\\{L, L^2\\}},\n$$\n\nwhere $C$ is a constant.\n\n## Lower Bound for GLMs (Theorem 2.5)\n\nFor any sensing matrix $A$, if $x$ is a uniformly chosen $k$-sparse vector, then any algorithm $\\varphi$ that attempts to recover $x$ satisfies:\n\n$$\nP(\\varphi(A, y) = x) \\leq \\delta\n$$\n\nonly if the number of measurements meets the condition:\n\n$$\nm \\geq k \\log(n/k) \\left[ 1 - h^2(\\delta) + \\delta k \\log(n/k) \\right],\n$$\n\nfor some mutual information term $I$ satisfying $I \\geq I(y_i; x | A)$ for all $i \\in [m]$. Specifically, when $y$ takes binary values ($y \\in \\{-1, 1\\}$), the expected squared inverse link function satisfies:\n\n$$\n\\mathbb{E} [g(A_i^T x)^2] \\geq I(y_i, x | A),\n$$\n\nwhere the expectation is taken over the randomness in $A$ and $x$.\n\n## Update After Rebuttal:\n\nI think the authors addressed my review sufficiently, and vote to accept the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your constructive and positive review. \n\nThanks also for suggesting the additional reference. We will cite this paper as a relevant lower bound for sparse recovery. Since the input signal is binary in our case, the lower bounding techniques are somewhat different, as we can use information theoretic inequalities directly. \n\nRegarding the strong assumptions on the measurement matrices, we would like to mention that our lower bounds (sec 2.2 and Thm 2.5) work for any family of measurement matrices. Regarding the upper bound: we can make Thm 2.1 work for a more general class of matrices, at the expense of some clarity. Indeed, the only property of the Gaussian measurements that we use, conditioned on other assumptions of the theorem, is centered-ness, and Stein’s lemma. So the theorem holds for other matrices too, albeit will result in slightly complicated expressions (see some more details in the response to Reviewer mHu2).", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing proofs.", "methods_and_evaluation_criteria": "This is a theoretical paper, and this does not apply.", "theoretical_claims": "I checked the first 9 pages and they seem fine to me.", "experimental_designs_or_analyses": "This paper does not have experiments.", "relation_to_broader_scientific_literature": "The work builds on the foundational ideas from compressed sensing and sparse linear regression as developed by Candès et al. (2006), Donoho (2006), and Tibshirani (1996). The literature on one-bit compressed sensing—initiated by Boufounos and Baraniuk (2008) and later refined by Jacques et al. (2013)—has dealt with the challenges posed by extreme quantization (only sign information is available). This paper extends that line of work by incorporating Gaussian noise before quantization (the 1bCSbinary model), and it rigorously shows that the sample complexity remains optimal ($O((k+\\sigma^2) \\log n)$) even when only sign information is used.", "essential_references_not_discussed": "I wonder if it might make sense to also cite work on lower bounds for sparse recovery (such as \"Lower Bounds on Sparse Recovery\" (Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff)), since they also have these communication complexity style proofs.", "other_strengths_and_weaknesses": "### Strengths:\n\n1. The paper has a unified treatment of multiple regression models. \n2. The proposed algorithm -- linear estimator followed by top-k, is simple. \n3. The insight into not having a stat-comp gap here is interesting. \n\n### Weaknesses:\n\n1. Many of the results make strong assumptions on the measurement matrices. \n2. I feel the paper doesn't communicate the main novelty in analysis or algorithm clearly.", "other_comments_or_suggestions": "None", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V7WR9Jl8rc", "reviewer": "Reviewer_h1gw", "summary": "The paper studies the problem of recovering sparse binary vectors from noisy generalized linear measurements. For simplicity I am stating the special case problems SparseLinearReg and 1bCSbinary here: $x \\in$ {$0,1$} is the unknown $k$-sparse vector that needs to be estimated. $A \\in \\mathbb{R}^{m \\times n}$ is a sensing matrix (possibly random) with the power constraints $E[(A_i^\\top x)^2] \\leq k$. The $m$ linear observations using that matrix are the entries of the vector $y = Ax + z$ for SparseLinearReg or $y = sign(Ax + z)$ for 1bCSbinary. The goal is to use an appropriate $A$ and algorithm that takes $y$ and produces $x$ which is correct whp. The more general version of the problem uses generalized linear measurements using a link function in the standard way, which captures the above two problems as well as Logistic Regression as special cases. The paper uses $A$ having standard Gaussian entries and a very simple algorithm from Plan et al., 2017 that works by outputing the $k$ heaviest elements of the vector $(\\langle y, A_i \\rangle)_{i \\in n}$ (which intuitively will correspond to the support of $x$ because $y$ is correlated with $A_i$ iff $x_i=1$). That way, the paper gives an upper bound for the sample complexity (achieved by the aforementioned computationally efficient algorithm) of the general problem, which yields corollaries for each of the three problems, SparseLinearReg, 1bCSbinary and LogisticRegression. Notably, if $m = \\Theta((k+\\sigma^2)(\\log(k) + \\log(n-k)))$ only the sign information in $y$ is enough in linear regression (i.e., 1bCSbinary is not harder than linear regression in that regime). The upper bounds also contradict the conjecture from Gamarnik and Zadik 2017 that no computationally efficient algorithm can exist for SparseLinearReg with the provided sample complexity. The paper provides an information theoretic lower bound based on Fano's inequality for the general problem which gives corollaries for each of the 3 problems. This gives tight characterization of the sample complexity for 1bCSbinary LogisticRegression. Finally, for exact recovery in SparseLinearReg, the authors complement the lower bound with an analysis of the MLE that gives almost a matching upper bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful and positive review of the paper.  Regarding your question, for the 1bCSbinary problem, there is no computational-statistical gap, since the information theoretic lower bound matches with the sample complexity of the linear estimator (up to constants). However the constant factors can be different, and also for other GLMs it may be the case that there is a computational statistical gap depending on the quantities $L$ (in Thm 2.1) and the mutual information $I(y_i, x|A)$ in Thm 2.5. Hope this answers your question.", "claims_and_evidence": "The main body and of the paper contains proofs for the claimed results.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I went through the main body of the paper and the claims seemed reasonable. That being said, I have not done a thorough check of all the proofs.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper discusses related work adequately.", "essential_references_not_discussed": "I do not have additional suggestions.", "other_strengths_and_weaknesses": "**Strenghts**\n- Unified approach: the main result holds for the general problem that uses generalized linear measurements, and gives as corollaries the results for the three other problems.\n- The algorithm is very simple to state and is computationally efficient\n- It is interesting (and perhaps a bit surprising) that in the regime $m \\approx (k + \\sigma^2) \\log n$ only the sign information suffices for sparse linear regression.\n- The paper shows tight results for exact linear regression.\n\n**Weaknesses**\n- The gap between upper and lower bounds is hard to quantify, as the bound is expressed as some optimization problem.\n- It remains open problem to find an efficient algorithm with better sample complexity than $(k + \\sigma^2) \\log n$ for linear regression.\n\nOverall, I feel that the paper makes important contributions and would like to recommend acceptance.", "other_comments_or_suggestions": ".", "questions_for_authors": "Related to the conjecture in Gamarnik and Zadik, 2017, do the authors think that a statistical-computational gap still exists but for some weaker threshold for the number of samples?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AtNT8wL5pE", "reviewer": "Reviewer_mHu2", "summary": "The paper considers a new problem setting of recovering sparse binary vector from generalized linear measurements. The authors propose a simple algorithm based on Plan et al. (2017) and prove its performance guarantee, complemented by a nearly tight lower bound. This then implies tight resolution to noisy 1-bit compressed sensing and logistic regression. Interestingly, for SparseLinearReg, when $m = \\Omega((k + \\sigma^2) \\log n)$, keeping the sign information only suffices. Also, for SparseLinearReg, the authors prove tighter upper and lower bounds based on MLE.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for a careful review and all your interesting insights and questions.\nWe completely agree with the suggestions, minor issues and typos mentioned. We will incorporate them in the next revision of the paper. In particular, we will fix all the minor issues and typos, incorporate the suggestions including adding a table of results and defining a separate notation for a row vector and column vector of ${A}$.\n\nBelow we give responses to the questions asked.\n\n(Question 1) Your observation is correct. As you mentioned, there are other subgaussian distributions, for example, each entry of $A$ is chosen iid uniform on the set {0,1}  or {-1,1} that can be used as measurement matrices. The general proof technique will work for these distributions too. However, the theorem statement in its current form is true  only for a Gaussian matrix where each entry is chosen iid $\\mathcal{N}(0,1)$. The proof uses the fact that each entry of the measurement matrix has zero mean and uses the distribution of the entries while applying Stein’s lemma between (11) and (12). As you noticed, the proof outline can easily be used for any other  distribution on the measurement matrix. We will mention it in the revised version of the paper.\n\n(Question 2) This is an interesting observation. While there might be some relation to an optimization paradigm, instead of this being a  condition on the model, it can  be thought of as a definition of $L$ which determines the rate of convergence. Note that we can also write  $L:= \\min_{i\\in [1:m]} \\frac{\\mathbb{E}(g'(A_i^Tx))}{||y_i|| }$  or can omit it altogether and write $\\min_{i\\in [1:m]} \\frac{\\mathbb{E}(g’(A_i^Tx))}{||y_i||_{\\psi_2}}$ instead of $L$ in (7) (Theorem 2.1). Since $L$  could be vanishing with $k$ as is the case in this paper, as defined it will always exist. \nThe numerator in $L$ can also be written as $\\frac{\\mathbb{E}(y_iA_i^Tx))}{k}$ (see the series of transformations between (11) and (12) on page 7). This quantity has previously been used in Plan,  Vershynin, Yudovina, 2017. See the definition of $\\mu$ in proposition 1.1. This comes naturally while analyzing the convergence of linear estimator, since the estimator measures the contribution of each coordinate to the measurement outcomes.\n\n(Question 3) You are right. Thank you for noticing this. \n\n\n(Question 4) It turns out that for iid Gaussian design the avg error and max error criterions are equivalent.  Given any decoder $\\phi$ with good average error performance, we can design $\\phi'$ with good max error performance as follows:\n\nOn input $(A,y)$, sample a uniform $n$ dimensional permutation matrix $R$; compute $\\hat{x} = \\phi(AR, y)$, and output $R\\hat{x}$. \n\nThen, for any x, $\\mathbb{P}\\left(\\phi'(A, Ax+z)\\neq x\\right) =\\mathbb{P}\\left(R\\phi(AR, Ax+z)\\neq x\\right) =  \\mathbb{P}\\left(\\phi(AR, ARR^{-1}x+z)\\neq R^{-1}x\\right) = \\mathbb{P}\\left(\\phi(\\tilde{A}, \\tilde{A}R^{-1}x+z)\\neq R^{-1}x\\right) $ where $\\tilde{A} = AR$. $AR$ is  iid Gaussian design because if we take a uniform permutation of columns of a gaussian matrix, it is still iid Gaussian. Since $\\tilde{A}$ is i.i.d. Gaussian and $R^{-1}x$ is uniform $k$-sparse vector, this implies the max error of  $\\phi'$ is same as the average error of $\\phi$.\n\n\n\nThus, the conjectured hardness by Gamarnik and Zadik is true for both maximum probability of error and average prob of error. \n\nWe will mention it in the revised version.\n\n(Question 5) In the prior literature, $\\log(n/k)$ and $\\log{n}$ are not distinguished for the purpose of information-computation gap, which makes sense if $k = O(n^\\alpha)$ for any $\\alpha <1$. When $k = cn$ for some constant $c$, we can use an identity matrix to recover $x$ in $n$ measurements. Note that $k\\log{n/k} = O(n)$ in this case. Therefore altogether $\\log(n/k)$ and $\\log{n}$ may not be differentiated for the purpose of this problem.\n\n(Question 6)  We believe that you are referring to  the last equality on page 15. We should have added another step here. This comes by substituting the value of probability densities as we show below. For any $r$ and set $\\mathcal{V}$, the density  $p(y_r|A_{r,\\mathcal{V}}) = \\frac{1}{\\sqrt{2\\pi\\sigma^2}}e^{-\\frac{y_r-A_{r,\\mathcal{V}}^2}{2\\sigma^2}}$. Thus,   $$\\mathbb{P}\\left(\\sum_{r}\\log{\\frac{p(y_r|A_{r,\\mathcal{U}})}{p(y_r|A_{r,\\mathcal{S}})}}>0\\right)  = \\mathbb{P}\\left(\\sum_{r}-\\frac{(y_r-A_{r, \\mathcal{U}})^2}{2\\sigma^2} + \\frac{(y_r-A_{r, \\mathcal{S}})^2}{2\\sigma^2} >0\\right) $$ The last quantity here can be manipulated to get the last equality on page 15.\n\n(Question 7) You are right. In principle, the bounds of Theorem 2.9 and 2.10 can be extended to GLM observations. Though, it will be more difficult to analyse them as the probabilities will be more complex. We did not try to extend it for one bit compressed sensing and logistic regression because the given upper and lower bound already match up to constants. Recall that we can use an identity sensing matrix when $k$ is linear in $n$.", "claims_and_evidence": "See Theoretical Claims.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I checked all proofs and concur that they are generally correct. There are some minor issues and typos regarding absolute constants and tightness of the results, but the orderwise guarantees remain intact. Typos are deferred to the end. Here are some minor issues that I saw:\n\n1. In line 338 (second column), it should be $y_i(A_{i,j} - A_{i,j'}) - E$, not $y_i(A_{i,j} - A_{i,j'}) - 1$.\n2. In the proof of Theorem 2.5, when Fano's inequality is applied, why is there a \"+1\" in the $\\log\\left( \\binom{n}{k} + 1 \\right)$? To my understanding, the total number of possible k-sparse binary vectors is precisely $\\binom{n}{k}$? Then one could bound $I$ as $I \\geq (1 - \\delta) k \\log \\frac{n}{k} - h_2(\\delta)$, yielding a slightly tighter inequality.\n3. In the last part of the proof of Theorem 2.5, when the authors invoke the result of Topsøe (2001), there is a $\\log 2$ missing. Also, the range of $t$ should be $[-1/2, 1/2]$, not $[-1, 1]$.\n4. In many parts of the other proofs (e.g., Proof of Theorem 2.10), the authors use the inequality $\\binom{n}{k} \\leq n^k$. It may be minor, but still I would prefer if the authors write the proofs and statements via $\\binom{n}{k} \\leq \\left( \\frac{en}{k} \\right)^k$.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "- To the best of my knowledge, tackles a new problem setting\n- Nearly tight sample complexity bounds, which cannot be obtained by prior algorithms nor analyses\n- Interesting proof techniques that may be of interest for statistics and information theory community", "essential_references_not_discussed": "None to the best of my knowledge.", "other_strengths_and_weaknesses": "**Strengths:**\n1. Clearly and well written\n2. Simple yet effective resolution to the well-studied statistics problem with tight theoretical guarantees extending to GLM observations.\n3. Although the proof flow itself is standard in information theory and statistics, there are several novel details that I appreciated: correlation vs. uncorrelation based on the support of $\\bf{x}$ and appropriate use of independency arguments (virtually all theorems, to my understanding), coupling(?)-based tighter lower bound for SparseLinearReg (Theorem 2.10).\n\n**Weakness:**\n1. Given the algorithm's simplicity, it would have been better to include some toy experiments that showcase the tightness of the theoretical results presented.\n2. Writing can be overall improved; see below.", "other_comments_or_suggestions": "Typos:\n1. The notation $\\bf{A}_i$ is used interchangeably between column vector and row vector throughout the paper. For instance, in Eqn. (2), $\\bf{A}_i$ is the row-vector, but then shouldn't it be $\\bf{A}_i \\bf{x}$, not $\\bf{A}_i^\\top \\bf{x}$? But then in Section 2.1, the same notation is overloaded with column vector. Also, in some parts, this is denoted as $A_i$ (e.g., line 360 left column).\n2. Line 52 (first column): $[1 : m]$ is not defined\n3. Line 91 (second column): Guassian => Gaussian\n4. Line 128 (first column): Theorem 2.8 => Corollary 2.8\n5. Line 639: what is the definition of $Q(\\cdot)$?\n6. Line 754: what is the definition of $h$? Actually, it seems that this is defined in line 978 as the differential entropy.... It should be defined sooner\n7. Line 801: $\\bf{x}' \\Rightarrow \\tilde{\\bf{x}}$\n8. Line 1085: Jenson => Jensen\n9. In Theorem 2.10, $\\max_l \\Rightarrow \\max_{l \\in [1:k]}$\n\nSuggestions:\n1. I would suggest putting in a table comparing prior results and the results shown in this paper. Right now, all the comparisons to prior works are crammed into Section 1.1, which was a bit hard for me to parse at first, and I had to go back and forth after going through the theorems. Also, the table would help the readers organize the theorem results more clearly, as they are subtly different depending on the setting: specifically, whether $A_{i,j} \\sim \\mathcal{N}(0, 1)$ or not.\n2. Some notations are left undefined, e.g., $\\lVert \\cdot \\rVert_{\\psi_2}$. The definitions should be included, at least in a footnote, for completeness.\n3. Line 913: maybe put in a reference for the inequality (Theorem 11.1.3 of Cover & Thomas (2006))\n4. Throughout the paper, I see things like [Example 2.5.8](Vershynin, 2018). If the authors meant to do \\citet[Example 2.5.8]{vershynin2018highdim}, which should yield Vershynin (2018, Example 2.5.8), the authors should fix the bibtex errors accordingly.\n5. Appendix B is too much not self-contained... The notations such as $s_1$, $K$, and $w_t$ aren't defined, as it seems that the reader must explicitly look them up in Plan et al. (2017)", "questions_for_authors": "1. The proof of Theorem 2.1 doesn't seem to utilize the fact that the entry is Gaussian explicitly; rather, the only facts used were 1. $\\lVert A_{i,j} \\rVert_{\\psi_2} \\leq C'$ and 2. it satisfies the power constraint (Eqn. (2)). Then are there examples of subGaussian distribution (not Gaussian) that satisfy the power constraint? Then maybe Theorem 2.1 can be written in a more general sense. One immediate example may be binary sensing matrix, with $A_{i,j} \\sim \\mathrm{Ber}(p)$ for some $p \\in (0, 1)$?\n2. In Theorem 2.1, what is the meaning of $L$? This reminds me of the Polyak-Łojasiewicz condition, with a statistical twist(?). What do the authors think? Also, are there (subGaussian) GLMs that do not satisfy this $L$ condition? Lastly, has this $L$ condition been considered before in the GLM literature?\n3. The statements of Corollary 2.2~2.4 should be either \"... if $m = \\Omega(...)$, or \"there exists a $m_0 = O(...)$ such that when $m \\geq m_0$, Algorithm 1 recovers the unknown signal\".\n4. The authors mention that the lower bound applies to the average error prob, while the upper bound is for the max prob. Then is there a chance that there may be a better algorithm (or better analysis) for deriving an upper bound for the average error prob, somewhat closing the gap between upper and lower bound ($k \\log n$ vs. $k \\log(n/k)$)? Or is the conjecture of Gamarnik & Zadik (2017a) basically saying that the gap (for now) is inevitable regardless of whether one looks at max error prob or average error prob?\n5. By the way, in the abstract, the authors mention that there is no statistical-computational gap for 1bCSbinary and logistic regression. Why is this the case? To my understanding, the upper bounds hold for $m \\gtrsim (k + \\sigma^2) \\log(nk)$ and the lower bound requires $m \\gtrsim (k + \\sigma^2) \\log (n/k)$? ($1/\\beta^2$ for logistic regression).\n6. In the proof of Theorem 2.9 (Appendix A.3), can the authors elaborate on the last equality (equivalent formulation of log likelihood testing)?\n7. Is there a combinatorial (or something similar) intuition behind $l = k \\left( 1 - \\frac{k}{n} \\right)$?\n8. It seems to me that the MLE-based approach is valid for GLM observations beyond SparseLinearReg, as we have a parametric assumption on the distribution, which makes $p(y|x)$ well-defined...? Then, am I correct in saying that the improved upper and lower bound arguments (Theorems 2.9, 2.10) cannot be extended trivially to GLM observations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of exact recovery of sparse binary vectors from generalized linear measurements and presents a simple linear estimation algorithm with sample complexity bounds; there were also nearly matching info-theoretic lower bounds. 

During the discussion, the authors authors addressed all comments raised to the reviewers' satisfaction. While no experiments were included, reviewers agreed this did not detract from the paper’s strong theoretical contributions. The strengths of the paper include its simplicity, clarity, and unification of several sparse recovery settings; this includes a nice insight that no stat-compute gap exists for 1bcs and logistic regression.

I encourage the authors to incorporate the reviewers’ suggestions to improve clarity; especially by fixing notation, defining constants carefully, and including a summary table of results. In all, this is a solid paper.
Decision: Accept (poster)