On learning sparse vectors from mixture of responses
Authors: Nikita Polyanskii
Venue: NeurIPS 2021 Poster (2021)
Keywords: sparse vectors
mixture of binary linear classifiers
1-bit compessed sensing
query complexity
noisy measurements

Abstract:  In this paper, we address two learning problems. Suppose a family of $\ell$ unknown sparse vectors is fixed, where each vector has at most $k$ non-zero elements. In the first problem, we concentrate on robust learning the supports of all vectors from the family using a sequence of noisy responses. Each response to a query vector shows the sign of the inner product between a randomly chosen vector from the family and the query vector. In the second problem, we aim at designing queries such that all sparse vectors from the family can be approximately reconstructed based on the error-free responses.  This learning model was introduced in the work of Gandikota et al., 2020, and these problems can be seen as generalizations of support recovery and approximate recovery problems, well-studied under the framework of  1-bit compressed sensing.  As the main contribution of the paper, we prove the existence of learning algorithms for the first problem which work without any assumptions. Under a mild structural assumption on the unknown vectors, we also show the existence of learning algorithms for the second problem and rigorously analyze their query complexity.

On learning sparse vectors from mixture of responses
Nikita Polyanskii IOTA Foundation
Berlin, Germany
mikitappoyymmsyyogmmsl.ccc
Abstract
In this paper, address two learning problems. Suppose family of l unknown sparse vectors is fixed, where each vector has at most l non-zero elements. In the first problem,
concentrate robust learning the supports of all vectors from the family using sequence of noisy responses. Each response to a query vector shows the sign of the inner product between randomly chosen vector from the family and the query vector. In the second problem, we aim at designing queries such that all sparse vectors from the family can be approximately reconstructed based on the error-free responses. This learning model was introduced in the work of Gandikota et al., 2020, and these problems can be seen as generalizations and approximate recovery problems, well-studied under the framework of 1-bit compressed sensing. As the main contribution of the paper, we prove the existence of learning algorithms for the first problem which work without any assumptions. Under a mild structural assumption on the unknown vectors, we also show the existence of learning algorithms for the second problem and rigorously analyze their query complexity.
support recovery
Introduction
Many digital data acquisition methods can be expressed as recovering an unknown real-valued sparse vector from linear measurements. Compressed sensing is a signal processing methodology proposed in g (5 make the process of vector reconstruction reliable and efficient. Criticism of classical compressed sensing is that it assumes infinite precision of real-valued measurements. One interesting setup for compressed sensing is that the measurement outcomes are quantized, e.g., only signs of measurements are captured. Different aspects of the 1-bit compressed sensing problem have been extensively investigated in recent years [
One important sub-problem that often arises in 1-bit compressed sensing is to learn the support of an unknown sparse vector. A vast body of literature focuses on this task and gives bounds on the minimum number of measurements
16
1 B
sufficient for support recovery I 16 13].
In this paper, we investigate model which can be seen generalization of 1-bit compressed sensing. In this model, family of & unknown sparse k-sparse vectors in R" is fixed, and the response to query vector shows the sign the inner product between the query vector and vector picked uniformly at random from the family. The goal is to reconstruct the vectors (or only the supports of the vectors) using the least number of queries. real-life applications, the measurements are suffered by noise, which causes sign flips. Thereby, we also suggest considering a variation of the model that admits adversarial noise.
Our problem statement is in spirit of many machine learning models, e.g., a mixture of linear regression models 77 19 27
29 6 and a mixture of binary linear classifiers [29]. However, we stress an important difference from the classical machine learning setting: in our model, one constructs data points and oracle provides the label for each of them; the goal is find the minimal number of data points sufficient for learning all the components in a mixture of binary linear
21 17
30
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

classifiers. Recent works on mixture of sparse linear regressions considered a similar setting and
studied query complexity of learning algorithms [3] 23 20].
The most relevant research to our work is provided in 14 where the noiseless version of the proposed model was discussed and some single-stage and two-stage learning strategies were provided. The main technical contribution presented in that paper is an algorithm for finding the support of the sparse vectors. However, its main drawback is that for three or more unknown vectors, it was shown to work only under the support separability assumption: the support of any unknown vector in the family is not covered by the union of the supports of the other unknown vectors (c.f. Table I The authors left the problem of support recovery without any structural assumptions as an open problem. We also highlight that for family of two unknown sparse vectors, the authors of [14] provided a polynomial time algorithm for the approximate reconstruction of both vectors that works under a mild assumption.
Since the first submission of this work, the authors of [15] have developed additional theoretical results for the robust support recovery problem. Specifically, using various tensor decomposition techniques and constructions of union-free families, it was shown how to efficiently learn with high probability the supports of all unknown vectors without any assumptions (c.f. Table D.. For certain structural assumptions on the support of unknown vectors, it was also shown how to improve the query complexity.
1.1 Our contribution and technique
Our main contribution lies in showing the existence of learning algorithm that works without any assumptions and is resilient to noisy measurements. Suppose a family of l unknown k-sparse vectors in T is fixed. For any given subset Q C [n]. we first design queries that enable us to learn the number of vectors whose support intersects Q non-trivially. Based on this knowledge, we show how problem of quantitative group testing. In this problem,
to reduce the support recovery problem one needs to learn a hidden hypergraph defined over the set [xi] with É edges each of size at most k. The response
query Q C [n] shows the piercing number, the number of edges overlapping with Q. Here, we arrive to the concept of (f, k. a) roburro---rroolllllll us uniquely reconstruct any hidden sparse hypergraph based on sequence of responses. In the combinatorial coding theory literature, this concept was analyzed only when & = 1, a = 0 [26). We extend this line of research for k 2 1 and a 2 0 and give an achievability bound for robust-resolvable matrices. In particular, we show connection between robust-resolvabee matrices and a notion that generalizes cover-free families which were previously investigated in extremal set theory 28 [2]. We highlight that the use of some specific subclasses of generalized cover-free families such as union-free families and pairwise independent union-free families was already discussed the context of various 1-bit compressed sensing problems [14 1 [6]. However, such link was used before either in very specific setting, e.g., l = 1, or under certain assumptions. We note that all queries of the proposed support recovery algorithm can be carried out in parallel (Theorem
matrices (Definition I that allow
Once the supports of all unknown vectors in the family are reconstructed, it remains to recover the values of these vectors. We consider this task in the noiseless setting and make an assumption: (a) the support of any unknown vector not fully contained in the support of any other unknown vector from the family, and (b) the magnitude of each entry can be bounded from below and above. It is known that Okk/c (og(n/c) simple Gaussian queries are sufficient to learn an unknown k-sparse vector in RR using only signs of linear measurements [8]. Thereby, one natural idea to recover the family of vectors to model Gaussian query for every given unknown vector from the family. A similar technique was also used in [4], however, our solutions work under a milder assumption. In simple tto-stage recovery process, we carry out queries required for the approximate reconstruction at the second stage after getting responses to queries used for the support recovery (Theorem 2 In more sophisticated non-adaptive solution, we re-use the concept of cover-free free families that enable us to emulate individual Gaussian queries for any potential family of l unknown sparse vectors (Theorem B
We emphasize that our contribution is primarily theoretical as the questions raised in our work are purely mathematical. For instance, we leave the problem of designing query scheme that allows for an efficient reconstruction algorithm with running time polynomial in the number of queries as an open problem. However, our research has relevant practical applications since the considered model can be used for modeling complex systems with heterogeneous data. According to [14,, studying

---

different aspects in such a model would help analyze recommendation systems where the privacy of user's data has be preserved.
1.2 Outline
The remainder of the paper organized as follows. We introduce some notations and describe the problem statement in Sec. [ Our results are summarized in Sec. Sec. describes robust support recovery algorithm and introduces useful concepts required for the algorithm. We present our approximate recovery algorithms Sec. Finally, Sec. conclldes the paper and discusses some open research directions. The proofs many statements are deferred to the supplementary material.
2 Problem statement
For simplicity of presentation, hereafter one-based numbering is used and log stands for the base- two logarithm of n. Let H2(a) denote the binary entropy function, i..., H2(a) = -a -a log a (1 a) log(1 a). The set of integers from to is abbreviated by [n]. A vector is denoted by bold lowercase letters, such as æ; and the i-th entry of the vector æ is referred to as T4. A binary matrix is denoted by uppercase letters, such X, and the entry in the i-th row and the j-th column written as Xi.j-
We say that vector support vector æ, written as supp(æ), denotes the set of coordinates corresponding to non-zero components of æ. We write 1 { to denote the indicator function of event A. For an integer vector æ E T and an integer r, 0 < r < m, define the Hamming ball centered at æ with radius r as (x) {y 2m (x. y) r). where du (æ, y) denotes the Hamming distance between and y. We will use the standard notion (o-morm written as ||-112-
R" is k-sparse if it contains at most k non-zero components. The
Let B ( ................................ ( } be family of l unknown k-sparse vectors in 1n such that g
for all i e [d]. Throughout the paper we assume that the number of vectors not too large and the vectors are indeed sparse. Specifically, let lk o(n)). Suppose that an oracle returns a (noisy) output
E 1} for given query vector x E R". [g]:
sign( (0) ,),) M/-
(1)
where the random variable 3 is sampled uniformly at random from the set B, the value E {-1,1} noise, and the sign function is defined as follows
0, -1, a 0.
1,
sign(a:)
Clearly, for 7i- = 1, the resulting response is exactly the sign of the inner product between ( and G. For the approximate recovery problem, assume the noiseless case, i.e., 1/: for all [q]- For the support recovery problem, we make the only structural assumption regarding the noise level, namely:
L 1m== -13 S rq
for given real value E [0, 1). Our first goal is recover the supports of all unknown vectors.
Problem 1 (r-robust support recovery). Let be real value from the interval [0, 1] and B (a(1) "8."),..""" (3.)),3(f) such that with probability 1 O(1/n), based on a sequence of noisy binary responses yı..... My. provided that (1- is possible to find S1,...,,S St S [m] with
a family of & unknown k-sparse vectors in RR. Design queries (1)), ,..., (..),..., (44)
(S..... S2} (supp( supp(
Our second task to approximately recover the unordered set directions of unknown vectors with given precision in the noiseless setting. Formally, this problem can be stated follows.
3

---

Result
Query complexity
Assumption
the support of any unknown not covered by union the supports of other vectors
14
Theorem 1]
O(1)),1 n)
15
Corollary
O ((k) logellootttt 2+2 log n)
No
Theorem
Okkl max( 7 (2,k) log n)
No
Table 1: Comparison of query complexity for support recovery of unknown k-sparse vectors in IR..
Problem 2 (e-approximate recovery). Fix - O. Let > be a given real value and B {g(0) .e.......))) be family of 8 unknown k-sparse vectors in RR.. Design queries _!.))..... al))) such that with probability 1 -0(1//)) based on the sequence of binary responses yı...., Yg provided that 1 22. it is possible to reconstruct the unknown vectors with precision e, Le., find k-sparse
vectors B
B
E IR" satisfying the inequality
B ( c,
max VE(E]
where a : [8] - [E] is some bijection (permutation).
Our results
In the following three statements, summarize main results concerning the above problems.
First, we show the existence of a robust support recovery algorithm without any assumptions.
Theorem (Robust support recovery algorithm). Let B {1((1) ..... ((())) be a family of unknown
k-sparse vectors in R Let E [0, 32t
where
p' min(e, k)
min(f,A)
(1-
min(E, 2ki-min((.A)
(3)
2kl
2kl
Define
((),,,))= := (2 - 1) log(1 -p') 2- logp' - H2
Then there exists a r-robust algorithm to learn the support of all vectors in B with probability at least 1 O(1nn) using
(2ke 1) log (1 o(1)
w((66T, E, k)
non-adaptive queries, where is Euler's number. For the noiseless case 0, the query complexity can be estimated as
Okk max(2el, mek)min(E.R) log n).
For the noiseless case T = O, we compare our query complexity for the support recovery problem with the results of prior work [14] and parallel paper (15) in Table Similar to f15) and unlike (14), we don't impose any structural assumptions on the unknown vectors, which may make the learning problem much simpler. The main drawbacks of our recovery algorithm are: (i) the running time is exponential in l and (ii) the query complexity is exponential in min E) log (og(maxx( kk, E)). Our solution outperforms the one from (15] for small enough k. say k ollog E). We believe that the dependence on k and & is not optimal in all existing solutions and it is possible to further improve the query complexity. For instance, for the degenerate case k and 7 O. also show the existence queries. In our proof. we think that the employed construction of robust-resol resolvable matrices via robust cover-free codes is far from an optimal one (Lemma 5). As for converse bounds in the noiseless setting, from simple counting arguments, follows that the number of queries in the support recovery problem has to be at least 2 log(E+1) log n). Recall that for 1,
Remark 1.
of an algorithm with O ((A Flog"
log
1² the number of queries required for finding the support of the unknown vector is at least 2 log
logn)
which is implied by 11

---

Let us introduce a mild assumption required for the approximate recovery problem.
Assumption 1. Let B { ..... . be famity of t unknown k-sparse vectors in R". For every i # j. the support of the i-th vector from is not contained in the support of the j-th vector from B, Le., supp(B(() supp(g(i) + 0. Some bounds on the magnitude of non-zero entries in all vectors from B are given, e.g,, that 0 O.
I 18 S exp(O(n)) for all j E [m]] and i [1] such
Recall that the approximate recovery problem is considered in the noiseless setting, i.c., T 0. Now show the existence of query algorithm which can be performed in two (non-adaptive) stages. Theorem Stwoestage approximate recovery algorithm). Let e > 0 be a real value. Let = 7 Then there exists an algorithm to recover all vectors in B with precision with probability least I O(L/n) using
(3(0) ......3)) 3 be family of vectors as in Assumption
o kE (kee max(2el, bek)min(t..))) log" n n log(k/c) log((/)))og(n/e))
kdd
queries that can be asked in two (non-adaptive) stages.
Finally, we present result concerning the existence of non-adaptive learning scheme.
Theorem 3 (Single-stage approximate recovery algorithm). Under the condition of Theorem there exists an algorithm to recover all vectors in with precision e with probability at least (1/n) using
( 2.203
o
max(2el, min(k)) log log(n/c/) log(k/c)
non-adaptive queries.
4 Robust support recovery
For a set Q S [n] and a family = (3(1) (((), of unknown k-sparse vectors R", we define the piercing number of Q in B as
pir Qi = Σ )
In Sec. 4.1
we first show how to learn this number with overwhelming probability by asking the same query multiple times. Sec. 4.2 we rephrase the support recovery problem the language of quantitative group testing and introduce the concept of robust resolvable matrices. The existence of such matrices discussed Sec, 4.3 and Sec. 4.4 Finally, in Sec. 4.5 we give a proof of Theorem
4.1 Estimating the piercing number
Let Q S [n] and æ = (ai...., xn) be a vector such that the i-th entry is sampled independently from the continuous uniform distribution U(0, 1) if i Q and is 0 otherwise. For integer m (divisible by 168), define
x. (1)
x (m/22 x
and
x (m/2+1)
x (m) x.
For every i E [m]] let y be noisy response defined as in (I. Let round(y) be function that takes real number 7 as input and outputs the closest integer number. Define sample statistic that estimates B)
m
pir(Q, () == round
Σ yi
Σ
Vi
im//2+]
Lemma (Piercing number estimator). Suppose
m 1/1 = - 11 < m
Then it holds that
Toe
Pr pir(Q, m)) = pir(Q, B)
- exp( (opl-st(mt-
5

---

4.2 Quantitative search model for sparse hy hypergraphs
hypergraph is a pair H E), where V is set of vertices, and E is a multiset of non-empty
subsets of V called hyperedges. A hypergraph H = (V, E) is said to be (E, ---paasssseeeeeee if the number of hyperedges is and the size of each hyperedge is at most Let E {ei... ,,,,),,, EE). For subset
Q S V. define the integer output =QQ, H) as follows
(Q, H) = Σ +()
(4)
==1
We now introduce the hypergraph His (V, EB), where the vertices V [n] and the set of hyperedges Es = [er,..... ee} contains hyperedges with e; = supp(33)) for all E [C]. Note that without any assumptions, the edge set Eg can possibly contain a hyperedge with large multiplicity if some vectors in B share the same support. Clearly, Hg is (f. -sparsee and z(Q HB) = pir(Q, B). In next statement, we derive an obvious extension of Lemma
Let B be a family of unknown sparse vectors and QQ....,Qu. Qm S [n] be a sequence of subsets. Set (=(Q1, Hg),..., z(Qm. HB)). Let be noise parameter such that O S. Te: Then there exist queries a!1), ,..., xl9)
Lemma 2.
1
IK" with q = ( log(ma)) such that with probubility .....,
1 - O(1/n), bused sequence of binary responses ".,..... ,,yg provided that 2 it is possible to reconstruct at least one E 2 such that du (2, 2) S 16rEm.
Let X be a binary matrix of size m x n, and H = (V, E) be hypergraph with V = In]. Set Q: supp(X;), where X; is the i-th row of X. With a slight abuse of notation, we denote by
z xX, H = (Z)...., 2m)
the sequence of integer responses, where 2; (Qi, H) is computed as in Lemma naturally motivates us introduce notion of robust resolvable matrices.
Definition (Robust resolvable matrix). Fix real number cx, 0 < a < 1/2, and integers E, > 1. matrix& X of size m x n said to be (f, kt a t-rrobut-resolvabll for any two distinct (f, k))-parse hypergraphs H1, H2, the corresponding Hamming balls centered at x =(X, H1) and xXX, H2) with radius am are disjoint, i.c.
(1), H2)) 2 2am +
By m(n, E, k. a:) denote the minimal number of rows in an (e, k, a) i--robut-resollvare matrix with n columns. Up to our best knowledge, Definition for > (and a 0, k: 2 2) new in the literature. We proceed our discussion with the simplest case & = 1 which might seem degenerate. However, the corresponding analysis already non-trivial and sheds light on the existence of robust resolvable matrices.
4.3 Existence of (4, 1,1,0)-oobuutt-rsoovabbl matrices
We now review literature (e, 1, 1100)rreollvbbl matrices. The best known explicit constructions come from number theory [4] [2] and are closely related to the concept of BCH codes. They have n columns and m f log r1(1 o(1) rows. For É 2 3. the best currently known resolvable matrices are all inexplicit and constructed by random coding as shown in 26 10).
Lemma 3. For any given integer f, there exists an (e, 1, resolvable matrix of size m n with
28
m
log
22 (2
log (()))
Furthermore, logng/ log ((1 + o(1) as oc. Remark 2. The presented existential result is order-optimal. By 110 8). the number of rows in an (e, 1, roout)-abbuutteesslvallllll matrix with n columns has be m 28 logn/ log f(1 + o(1))
4.4 Constructing robust resolvable matrices via robust cover-free matrices
challenging to find sufficient (and necessary) condition for a matrix to (f, k, -obuustt resolvable. In the following statement, make step toward understanding this problem.

---

Lemma 4, Suppose H1 = (V, 31) and H2 = (V, E2) are two different (f, -spare hypergraphs. Then there exists a query Q V of size at most min(f, k) that separates the hypergraphs, i.e. =(Q, H1) * =Q, H2).
Proof. Since two hypergraphs are distinct, there exists at least one hyperedge such that one edge set (E₁ E2) contains it with larger multiplicity than the other one (E2 Ei). We take the largest hyperedge with this property. Without loss of generality, let my and m2 be multiplicities such that is included, respectively, to F with multiplicity mi and Eg with multiplicity m2g l 2 m. > m2 2 O. For vertex v, define the set of hyperedges in a hypergraph H = (V, E) that are incident to this vertex
A(u, {e' E vEd).
Consider the set of hyperedges Nose A(v, H1). It includes mi copies of and possibly some other hyperedges E' C Ej. We observe that the set of hyperedges Nwee A(v, H2) includes m2 copies of e and precisely the same set of hyperedges E". This happens due to the choice of e. Thus, we obtain
mi + |E =
A
A(v, Hi)
>
n VEE
A(v, H2) = =m + EE".
(5)
JoEe
Toward a contradiction, assume that there is no Q S such that
=Q, H1) = U
A(v, Hi) +
U NEQ
A(v, H2) = =QQ, H2).
FEQ
This means that the above unions for any Q S must have the same size. By the inclusion-exclusion principle
A(t,HH)) = Σ
(-1)197+1
n
A(u, H1)
PEQ
D7Q'SQ
PEQ
Therefore, by induction on the size of Q, one can derive
n
A(u. H1)
n NEQ
A(v, H₂)
tEQ
for all Q C e. This contradicts to when c.
The above arguments show that proper query Q could have size at most f. Assume that =QQ Hi) > =Q, H2). Note that =(Q, H1) < k since Hi contains k edges. Thus, one can remove at least m0 QI - k) vertices from Q to get a subset of vertices Q' such that the output result for H1 is not changed, i.e., 2Q'', H1) z(Q, H1). On the other hand, it is clear that 2(Q', H22 S x(2, H2). This completes the proof.
Lemma suggests way for constructing (E, robust matrices. We now introduce a concept that generalizes the definition of cover-free codes. This family of codes was originally suggested in (24 connection with cryptographic applications.
Definition 2. A binary matrix X of size m is said to be f, rroou-a---oustt-oee---reeeee if for any disjoint subsets of columns U, W C [n] of size [U] = c and [W] = f, there exists at least 2am + 1 rows S [m] such that
X 1
for i [7 EU
X, = for all E [T] W.
If 0, then a (c. f, rohustt-ccee matrix is simply called (c, --cover-eeeee
An (1, f. a:) robuss--oveerr-eeeeeeeeeeo free matrix is also called robust union-free The latter has several applica- tions in 1-bit compressed sensing [6]. Now we state a straightforward corollary of Lemma that enables us to construct robust resolvable matrices.
Lemma 5. Suppose a binary matrix of size m x i (minn(e k), 2kl min(l, k), a) (.),aa)-ouuust-eee -ooustt--ove
free. Then X is (e, k, a) relllllalll......lle...
7

---

Proof. Let H1 (V, and H2 = E2) be two distinct (E. -sparre hypergraphs. By Lemma 4
there exists query Q S V. [Q] I min(e, k), such that xQ2 H1) * 2Q2, H2). Define W to be {v and W _ [m]. [W] < 2 min(L, k). Combining these arguments with the fact that is (min(e, k), 2kl min(f, k), a)) roobust-oroess yields that X is (c, k, aeroka.orrruuuutttteeaa robuss-reeollaabblle
E En U }2) Since we associate V with [n], we get Q S [n]. Q < min k.).
Fundamental limits of cover-free matrices have been subject of extensive studies in many papers [2]
28 However, we cannot directly apply known bounds since they correspond to the case = O. Now we present an achievability bound for robust cover-free matrices.
Lemma 6. Let c 2 1 and be integers, be real number from the interval (0.//2). where
p ( (tt)) (c+F)'
Define
g(7 e, f) == (2 log Then there exists (c, [, co.ffaa)-robus--oove--reee matrix of size m such that
(1- P) 2n log H2((?)).
m (c+ 1--f-1177 11-1) log n (1 + o(1).
g)
Using the above statement, we show an existential result for robust-resolvable matrices. Lemma 7. Let E 2 1 and k 2 be integers, be real number from the interval (0. /2). Let pl and w(r, k) be as in Theorem Then there exists an (f, k. resstttaee-e matrix of size m x n such that
(2ke 1) log
w(a, kkk)
For a = O, we have
m(n, e, o) (kl max(2el, 2ek) min(())))))))) logn).
Proof. The statement is implied by Lemma and Lemma with min(e, 28h min(E.))
4.5 Proof of Theorem
Let == - ( (00 be family of unknown k-sparse vectors. Let H8 = (V, E&) denote the (E, -s-arse hypergraph induced by i.e., the of edges Eg consists of the supports of vectors matrix X of size w(a.t,k) (1+) By Definition Hs can be uniquely recovered based on any noisy version & E nd of the vector 2(X, HE) so that di d 2(x, HB)) < amn. Applying Lemma 2 with overwhelming probability one can learn some by asking q O log(um)) queries (11)) ..... ...-, (99)) and obtaining responses .1,---. - Bg provided that (1 Finally, reconstruct the supports of all unknown vectors, we apply Algorithm This algorithm uses function next(.) that takes an (e, -spaase hypergraph and outputs the next [E, k) -sparse hypergraph (here we assume some canonical order on the set of sparse hypergraphs). In other words, the algorithm involves enumerating over family of (E, -sprse hypergraphs. Thereby, g queries are sufficient for solving Problem
.....
from B. Set a 16 By Lemma 7 there exists an (f, kt roous-----ee
m x with
[246- 1) log
Algorithm 1: Support recovery algorithm
Data: (e, rou---rbu--esoollabblll matrix X of size n: noisy response vector & with d'r (xX, X, HB))
/+ exists by Lemma 7 +/
< om
/* found by Lemma 2 +/
Result: supports of the & unknown vectors, SI...., S C [n]
H + (V, E). where V = [n], E = fei..... (t), e, [k];
while d (X, H) 2) > am do
H + next(H)
/* outputs the next sparse hypergraph */
end
for
i 1 to l do S, x 6
end

---

Approximate recovery
Throughout this section, we assume that there is no noise in measurements, i.e., T O. Theorem enables us to assume that the supports of all sparse vectors are already known. Thus, it remains to approximately reconstruct the values of the vectors.
A query vector æ = (z1....., Fn) E R" is called Gaussian if each entry is sampled independently from Gaussian distribution (0, 1). We shall the following result which says that Gaussian queries allow to efficiently reconstruct any sparse vector.
Lemma (Approximate vector recovery, [88). Let 3 be an unknown vector in IR with || = For any > 0, there exists algorithm that takes responses to Gaussian queries ..... x(() E 12
with O E log 4) as input and outputs 3 R so that ||
Recall the response to a query in our model is taken uniformly at random from set of & possible responses. Therefore, we need to show how to model a response to a Gaussian query for any given vector from the family. Here, we will use our structural assumption regarding the support of vectors (c.f. Assumption D In Sec. 5.1 we show how to emulate individual Gaussian queries in our model. In Sec. 5.2 we present two-stage approximate recovery algorithm.
5.1 Modeling Gaussian query
Define Inf to be very large positive real number whose lower bound will be clear from the context. For query vector (æ1, (21,...,, Tnn) R² and integer [e]. write Inf(*) (a:) to denote the vector whose j-th entry
Tjj E Supp(3 or E Ut/ssupp(3"")
Inf (x)) =
Inf, otherwise.
Let O denote an all-zero vector whose length will be clear from the context and g E R" be Gaussian query. Fix an integer i [{] and some positive integer m. Set (1.i) = _.... x (m/2,s)
Inf(*) (g) and (m/2+11,5) = = (m.f) = (nf (0). Let yı,..., 3m be responses to queries (1.3). ;..., x (m.1), i.e., yj = (ag B3) with 3 being sampled uniformly at random from B.
Define sample statistic that estimates the value sign((g. ((g, ()))
2 m
VIA
sign(g, (00mm) m) round
Σ yj
Σ
Vi
+1
j=m/241
Lemma (Gaussian query estimator). Let B be family of sparse vectors that satisfies Assumption Then holds that
Pr si (00 m) sign((g,3(0)))
(pp(-((E-2m)))
5.2 Proof of Theorem 2
Let = (1 ....",..... (00) ((0) be a family of & unknown k-sparse vectors that satisfy Assumption Fix <> 0. First, we invoke Theorem 1 and with probability O(1/n), the supports of all vectors in B can be reconstructed using (kt max(2ef, 2ek) min((.)) log" n) queries. Note that the number of coordinates in the supports of the vectors is at most kl.
..... .(M.....)))........ Bg with R = O log ) being as in Lemma Applying Lemma with probability 1 O(ne è log =)-)) we can learn the value of sign((g (i) 3 (()))) for some [R] and i [f]. by making O log(nkl/c)) queries. By the union bound, all values (sign( (g)()))))))) (0000)8(0) jjj [R] i [4]} are reconstructed with probability 1 (1/n)) by making O log log(nkl/c) measurements. Finally, Lemma guarantees that all sparse vectors from B can be recovered with the given precision based on the set of values {sign((g)) (0)gn(())),,0 (()))))))))))))))))
At the second stage, we first generate Gaussian vectors ()),.,,
[R], ė [e]] Since kt O(n). the required claim follows.

---

5.3 Proof of Theorem 3
Let B = (33 ,,.."....,"""""" ....,,3(0) be a family of & unknown k-sparse vectors that satisfy Assumption Fix
6 >> 0. First, we apply Theorem I and with probability 1 O(1 (n),, the supports of all vectors in B can be reconstructed using (R:E max(2el, 2ck) 2ck)min(f,k) log" n) queries. Note that the number of coordinates in the supports of the vectors is at most kL.
It remains to approximately recover the entries of the unknown vectors by asking queries in parallel to the queries used for the support recovery. Let X be an (L, coverr--ee matrix of size m x n with m = (kk max(f, k) miin((k.) exppminn( k)) log 71) which exists by Lemma 6 Let R = O log ) be the number of queries required in Lemma 8 For j E [R], define G to be a real- real-valued matrix obtained from the binary matrix X by replacing I's by Inf's and O's by independent samples from a Gaussian distribution (0, 1). We define Inf (X) to be a real-valued matrix obtained from the binary matrix X by replacing I's by Inf"s.
We ask queries corresponding to rows of matrices (Tnr() GX)( : : [R]} multiple times. Let T denote the number of times a fixed query repeatedly queried. We set T 0 (o)((RR) Recall that all the matrices are obtained from an (e, (e.ke))-oveer-free matrix. This means that for
every j E [R] and [f]. there exist rows in G (X) and Inf' (X) that are Inf (g) and In (0) for some Gaussian query 9. Thus, by Lemma 9 with probability 1 - [[( one can learn sign((g ())) for some E [C] and some independent Gaussian query g j E [R]]. By the union bound, one can learn the set of values {sign( ,))))) : E [R]. i E [{]} with probability guarantees that all sparse vectors from B can be reconstructed with the given precision based the set of values ((.)) (3))) =j E [R]) E [[]]
1 1- 1-0(1/m) (1))n.. Finally, Lemma 8
Finally, we estimate the number of queries used at the second stage of the approxi- mate recovery algorithm as O O²* log(= k ) max(e, k) m))in((ke) exp(min((, R:)) log lognlog" ") Thus, the total number of queries sufficient for solving Problem _ can be estimated as te (3 max(2el, mek)miin(k.)) log n log( l)g(
Remark 3. We note the following improvement on query complexity the number of queries required in Lemma 8 can be additionally bounded as o(log n) (e.g.. it is applicable when = (2(olg n)- n)-1/2)). In such a case, one can generate (f, kł, re-orousstcooer--fee o and m = Okk max(e, k) mi)kk(k, exp min(f, k)) log n) and construct only two matrices G(X) and [x) in a similar way. By performing the rest of the same procedure, one can decrease the total number of required queries in 12 & log(?)) times.
matrix of size m x n with small positive
6 Conclusion
In this paper, we studied two problems that arise in recovering unknown sparse vectors from mixture of sign responses. For the support recovery problem, we found a completely non-adaptive solution that does not use any assumptions. This problem was posed in [14). In addition, the proposed algorithm is resilient to noisy measurements. When describing our result, we introduced the notion of a robust resolvable matrix and derived an existential result for such matrices. We leave the problem of deriving fundamental limits of this combinatorial object as an open challenging problem that can be of independent interest in computer science, coding theory, and combinatorics. For the approximate recovery problem, we suggested single-stap stage and two-stage reconstruction algorithms working under Assumption TT] Finding an algorithm for robust approximate recovery of a family of unknown sparse vectors without any assumptions remains a major open problem.
Acknowledgments and Disclosure of Funding
The work was conducted in part when Nikita Polyanskii was with the Technical University of Munich and the Skolkovo Institute of Science and Technology. The author indebted to Arya Mazumdar for bringing this problem to his attention. The research was supported by the German Research Foundation (Deutsche forschungsgemminschhff, DFG) under Grant No. WA3907/1-1 and by the Russian Foundation for Basic Research under Grant No. 20-01-00559.
10

---

References
[1] Jayadev Acharya, Amab Bhattacharyya, and Pritish Kamath. Improved bounds for universal one-bit compressive sensing. In 2017 IEEE International Symposium Information Theory (ISIT), pages 2353-2357. IEEE, 2017.
[2] Albert Ai, Alex Lapanowski, Yaniv Plan, and Roman Vershynin. One-bit compressed sensing with non-gaussian measurements. Linear Algebra and its Applications, 441:222-2399 2014.
[3] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Conference on Learning Theory, pages 192. PMLR, 2016.
[4] Raj C Bose and Sarvadaman Chowla. Theorems in the additive theory of numbers. Commentarii Mathematici Helvetici, 37(1):141 147, 1962.
[5] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEÉE Transactions information theory, 52((): -098 2006.
[6] Arun Tejasvi Chaganty and Percy Liang. Spectral experts for estimating mixtures of linear regressions. In International Conference on Machine Learning, pages 1040-1048, 2013.
[7] Yudong Chen, Xinyang Yi, and Constantine Caramanis. A convex formulation for mixed regression with two components: Minimax optimal rates. In Conference on Learning Theory, pages 560-604, 2014.
[8] Arkady Djackov. On search model of false coins. In Topics in Information Theory (Colloquia Mathematica Societatis Janos Bolyai 16). Budapest, Hungary: Hungarian Acad. Sci, pages 163-170, 1975.
[9] David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289; 1306, 2006.
[10] Arkadii D'yachkov and Vladimir Rykov. On a coding model for a multiple-access adder channel. Problemy Peredachi Informatsii, 17(2):26-3,, 1981.
[1]] Arkadii Georgievich D' yachkov and Vladimir Vasil'evich Rykov. Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii, 18(3):7-13, 1982.
[12] Arkady D' y'ycchkov, Pavel Vilenkin, David Torney, and Anthony Macula. Families of finite sets in which no intersection of sets is covered by the union of others. Journal of Combinatorial Theory, Series A, 99(2):195-25 218,,2118222 2002.
[13] Larkin Flodin, Venkata Gandikota, and Arya Mazumdar, Superset technique for approximate recovery in one-bit compressed sensing. In Advances in Neural Information Processing Systems, pages 10387-10396, 2019.
[14] Venkata Gandikota, Arya Mazumdar, and Soumyabrata Pal. Recovery of sparse linear classifiers from mixture of responses. Advances in Neural Information Processing Systems, 2020.
[15] Venkata Gandikota, Arya Mazumdar, and Soumyabrata Pal. Support recovery of sparse signals from a mixture of linear measurements. In Advances in Neural Information Processing Systems, 2021.
[16] Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya Nori. One-bit compressed sensing: Provable support and vector recovery. In International Conference on Machine Learning, pages 154-162, 2013.
[17] Mian Huang, Runze Li, and Shaoli Wang. Nonparametrie mixture of regression models. Journal of the American Statistical Association, 108(503):929-94) 2013.
[18] Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 59(4):2082-2102 2013.

---

[19] Abbas Khalili and Jiahua Chen. Variable selection in finite mixture of regression models. Journal of the american Statistical association, 102(479) 2007. 2007.
[20] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Sample complexity of learning mixtures of sparse linear regressions. In Advances in Neural Information Processing Systems, pages (0532-10544) 2019.
[21] Yuanzhi and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal complexity. In Conference On Learning Theory, pages 1125-1144. PMLR, 2018.
[22] Bernt Lindström. Determination of two vectors from the sum. Journal of Combinatorial Theory, 6(4):402-407, 1969.
[23] Arya Mazumdar and Soumyabrata Pal. Recovery of sparse signals from mixture of linear samples. In International Conference on Machine Learning, pages 7466-7475, 2020.
[24] Chris Mitchell and Fred C Piper. Key storage in secure networks. Discrete applied mathematics, 21(3):215-22 2288, 1988.
[25] Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Com- munications on Pure and Applied Mathematics, 66(8):1275 2013.
[26] Grigory Poltyrev. Improved upper bound on the probability of decoding error for codes of complex structure. Problemy Peredachi Informatsii, 23(4):5-18, 1987.
[27] Weixing Song. Weixin Yao, and Yanru Xing. Robust mixture regression model fitting by laplace distribution. Computational Statistics & Data Analysis, 71:128-137, 2014.
[28] Douglas R Stinson, Ruizhong Wei, and Lie Zhu. Some new bounds for cover-free families. J. Comb. Theory, Ser. A, 90(1):224-234, 2000.
[29] Yuekai Sun, Stratis loannidis, and Andrea Montanari. Learning mixtures of linear classifiers. In International Conference Machine Learning, pages 721-729, 2014.
[30] Taiyao Wang and Ioannis Ch Paschalidis. Convergence of parameter estimates for regularized mixed linear regression models. In 2019 JEEE 58th Conference on Decision and Control (CDC), pages 3664-3669. IEEE, 2019.
[31] Dong Yin, Ramtin Pedarsani, Yudong Chen, and Kannan Ramchandran. Learning mixtures of sparse linear regressions using sparse graph codes. IEEE Transactions on Information Theory, 65(3):1430-14511 1451, 2018.
12


Reviews:
[{"review_id": "qezgERwpe07", "reviewer": "Reviewer_zJ8u", "summary": "This paper considers the problem of reconstructing a mixture of (sparse) linear classifiers from (noisy) binary responses. For each query, a sparse vector is selected from the ensemble and the inner product of the query vector is returned (perhaps plus noise). At a first glance, it is surprising that it is even possible to recover the underlying vectors reliably. This was established by Gandikota, Mazumdar, and Pal in a NeurIPS 2020 paper. This submission builds on this work by removing a structural assumption. This is a theoretical contribution and there are no simulations.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "As summarized above, this paper considers the interesting problem of recovering the underlying sparse vectors from a mixture of linear classifiers. Each query returns the inner product with one classifier from the mixture plus noise. In the 2020 work, it was assumed that the support of each classifier vector is not contained in the union of the supports of the other vectors. This submission significantly relaxes this assumption to only require that no classifier vector's support is fully contained in the support of any other vector. On the technical side, it relies on combinatorial constructions, such as robust-resolvable matrices. I think that overall this is a nice theoretical contribution to NeurIPS, as it improves significantly on a 2020 NeurIPS paper, using some interesting new math.\n\nHere are a few items that I think might have improved this submission:\n-Graphical/cartoon illustration of the improvement in query complexity over the 2020 paper\n-Some discussion of any known impossibility results (e.g., lower bounds), even if trivial at this point\n-Numerical simulations to compare this method to prior work, esp. the 2020 paper. (Note that the 2020 paper includes both synthetic and real data.)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not have any concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "hLhPY12IcXz", "reviewer": "Reviewer_uLNB", "summary": "This paper answers a number of open questions in [12] and generalizes some of them significantly as well. The contributions of the paper are summarized as follows:\n\n1) The authors provide a querying scheme that can recover the support of all unknown vectors without any structural assumption on the unknown vectors. This result is a big step in the direction of answering a major open question raised in [12].\n\n2) The results for support recovery in this paper is also resilient to adversarial noise. The idea of using robust resolvable matrices for recovering the support under this condition is very interesting.\n\n3) The authors also provide a new technique for emulating Gaussian queries in this problem which works under milder structural assumptions than stipulated by [12]. Hence, this paper also results in improved results for Approximate recovery of the unknown vectors.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper provide significantly interesting results using a number of novel ideas. I believe that the paper is quite well-written but the exposition can be improved in some places. Below, I have mentioned a few questions/suggestions that should be resolved in the final version.\n\n1) In Theorem 1, how do we know that there exist a positive root of f(\\alpha,\\ell,k)? It would be good to characterize \\alpha_0 for different values of \\ell,k and visualize them in a plot.\n\n2) The proof of Proposition 1 needs to be described with more details. First, the expectation of the piercing number estimator need to be mentioned and secondly, show why the adversarial error+ error due to randomness does not cause an issue in computing the piercing number correctly. \n\n3) In Lemma 6, alpha is used to denote the real number in [0,\\alpha_0). Some other variable must be used.\n\n4) It would also be good to compare these results with the ones in a recent paper (https://arxiv.org/pdf/2106.05951.pdf) on the same problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "BIOTvZruoT", "reviewer": "Reviewer_xjw9", "summary": "The paper provides statistical upper bounds for the problem of learning a mixture of sparse vectors from signs of linear queries, both in the noiseless and noisy settings. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper studies the problem of proper learning of a mixture of sparse vectors from possibly noisy 1-bit quantized linear queries. \n\nIn the noiseless setting, the authors prove an information-theoretic upper bound on the query complexity that uses fewer technical assumptions than the main result of Gandikota-Mazumdar-Pal (Neurips '20). In the noisy setting, the authors prove a similar upper bound but for the weaker problem of support recovery under certain identifiability assumptions on the underlying mixture.\n\nThe paper introduces the use of a number of interesting coding theoretic principles (piercing numbers, robust resolvable binary matrices, robust cover-free codes) to a fairly challenging family of problems. \n\nDespite its contributions, I have several concerns -- primarily with how the results of this paper are presented -- which prevent a higher score. \n1. To complement their upper bounds, [GMP'20] give a concrete, easy-to-implement (ie., low degree polynomial-time) algorithm for the same problem, and also show numerical results on standard ML benchmark datasets. This paper does not provide any algorithmic upper bounds or experiments; indeed, the algorithm \"seems to\" involve enumerating over a family of sparse hypergraphs which can be exponentially large in either the sparsity or the number of components, or both. I doubt that such approaches can ever find their way to practical use cases such as recommender systems.\n2. I put \"seems to\" in the above comment in quotes, since I can only make an educated guess of what the algorithm does. The actual learning procedure for either problem setting is never spelt out anywhere clearly in the paper. This might be a presentation issue but a rather serious one. I'd suggest that the authors transparently introduce the recovery algorithms in terms of pseudocode.\n3. Remark 1 is a bit confusing (and in my view, misleading). The query complexity is exponentially worse than the bound in the noiseless case presented in [GMP'20], so I am not sure if it directly resolves the open problem posed in that paper. \n\n---\n\nI thank the authors for their responses. I am inclined to retain my score (but to be fair the authors, my above questions cannot easily be addressed in a rebuttal without a revision). Other reviewers seem to be viewing the paper positively, and I respect that. Overall, I would be fine with accepting the paper provided they clearly address the points above in their final revision.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "9VCt2tP2vL", "reviewer": "Reviewer_WBt8", "summary": "This paper studied two learning problems.\n\nFor the first problem, they aim at designing queries such that all sparse vectors from the family  can be reconstructed using a sequence of responses. Each response to a query  vector shows the sign of the inner product between the query vector and a random vector from the family. \n\nFor the second problem, they study robust learning using only the support of all vectors from the family in the setting in which a fraction of responses can be flipped.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strength: This paper studied two learning problems and provided some theoretical results.\n\nWeakness : \n\n1. The paper is poorly-organized and hence hard to follow. Due to the structure issue, it is not sure that the contribution is large enough.\n\n2. Reference starts at page 9, not sure if this violates the guidelines of the conference.\n\n3. Not sure the methods proposed in this paper are novel enough.\n\n4. Several 1bit compressed sensing papers are missing:\n\n“Learning and 1-bit Compressed Sensing under Asymmetric Noise’’\n\n“One-Bit ExpanderSketch for One-Bit Compressed Sensing.’’\n\n“On Fast Decoding of High-Dimensional Signals from One-Bit Measurements.’’\n\n5. Several mixtures of linear regression papers are missing:\n\n“Learning Mixtures of Linear Regressions with Nearly Optimal Complexity.’’\n\n“Learning mixtures of linear regressions in subexponential time via fourier moments.’’\n\n“Small covers for near-zero sets of polynomials and learning latent variable models.‘’\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not discussed. Societal impact is not directly discussed, but it's a theory paper, so it does not have a direct impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0BoXa1epi3R", "reviewer": "Reviewer_jx9h", "summary": "The paper describes a method to recover a set of sparse vectors, either their values or their supports, by sampling them at random and obtaining their linear measurement quantized to a single bit representing the measurement sign. The crux of the analysis focuses on (i) modeling the set of sparse vectors as a hypergraph, where each vector support corresponds to an edge; (ii) defining a set of linear observations of signals that translates into observations of edges in the hypergraph; (iii) demonstrating that given enough noisy edge observations from the hypergraph and for sufficiently simple regimes (number and complexity of the edges, and noise level), the set of edges defining it can be estimated at sufficient accuracy.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "There is significant sophistication in the analysis of the proposed method that makes the read a bit difficult, but the presentation is clear enough after a re-read. In particular, the connection between Lemma 1 and Lemma 2 is not sufficiently clear, but Lemma 2 motivates well the rest of the presentation.\n\nIn the results, it is not always clear how the noise level tau > 0 has an effect (e.g., Theorems 2 and 3). In fact, the differences between the two halves of Figure 5 are minor, even for the baselines.\n\nTo improve clarity, terms as \"precision epsilon\" should be defined; some minor typos (e.g., \"to recovery all vectors\"; h in the last row of Page 6) exist.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given the flexibility of the proposed framework, limitations with respect to results in the literature are discussed (e.g., Remark 1). The paper also mentions the fact that the computational effort of recovery is not being considered, and that the measurement vectors are considered in terms of existence rather than construction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews and subsequent discussion, it is clear that this paper is tackling a non-trivial problem and contains good results. However there are some concerns with clarity and writing, and we ask the authors to incorporate the suggestions given by the reviewers. There is also a suggestion to make it clear in the abstract and in the beginning of the introduction that the problems considered were actually studied before, and are not introduced by the authors.  
Decision: Accept (Poster)