Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements

Thank you very much for a careful review and all your interesting insights and questions. We 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}$.

Below we give responses to the questions asked.

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

(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. The 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.

(Question 3) You are right. Thank you for noticing this.

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

On input $(A,y)$, sample a uniform $n$ dimensional permutation matrix $R$; compute $\hat{x} = \phi(AR, y)$, and output $R\hat{x}$.

Then, 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$.

Thus, the conjectured hardness by Gamarnik and Zadik is true for both maximum probability of error and average prob of error.

We will mention it in the revised version.

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

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

(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$.

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.

We thank you for your constructive and positive review.

Thanks 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.

Regarding 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).