Support Recovery of Sparse Signals from a Mixture of Linear Measurements
Authors: Soumyabrata Pal
Arya Mazumdar
Venkata Gandikota
Venue: NeurIPS 2021 Poster (2021)
Keywords: Support Recovery
Mixtures of Linear Regressions
Mixtures of Linear Classifiers
Sparsity
Low Rank Tensor Decomposition

Abstract: Recovery of support of a sparse vector from simple measurements is a widely studied problem, considered under the frameworks of compressed sensing, 1-bit compressed sensing, and more general single index models. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers, where the goal is to recover supports of multiple sparse vectors using only a small number of possibly noisy linear, and 1-bit measurements respectively. The key challenge is that the measurements from different vectors are randomly mixed. Both of these problems have also received attention recently. In mixtures of linear classifiers, an observation corresponds to the side of the queried hyperplane a random unknown vector lies in; whereas in mixtures of linear regressions we observe the projection of a random unknown vector on the queried hyperplane. The primary step in recovering the unknown vectors from the mixture is to first identify the support of all the individual component vectors. In this work, we study the number of measurements sufficient for recovering the supports of all the component vectors in a mixture in both these models. We provide algorithms that use a number of measurements polynomial in $k, \log n$ and quasi-polynomial in $\ell$, to recover the support of all the $\ell$ unknown vectors in the mixture with high probability when each individual component is a $k$-sparse $n$-dimensional vector.

Support Recovery of Sparse Signals from a Mixture of Linear Measurements
Venkata Gandikota
Arya Mazumdar
Electrical Engineering & Computer Science Syracuse University
Hahcroğlu Data Science Institute University of California. San Diego La Jolla, CA 92093 arya@ucsd.edu
Syracuse, NY 13210
Soumyabrata Pal
College of Information & Computer Sciences
University of Massachusetts Amherst
Amherst, MA 01003 soumyabratapuumasscom eduu
Abstract
Recovery of support of sparse vector from simple measurements is widely- studied problem, considered under the frameworks of compressed sensing, 1-bit compressed sensing, and more general single index models. We consider gener- alizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers, where the goal to recover supports of multiple sparse vectors using only small number of possibly noisy linear, and 1-bit measurements respectively. The key challenge is that the measurements from different vectors are randomly mixed. Both of these problems have also received attention recently. In mixtures of linear classifiers, an observation corresponds the side of the queried hyperplane a random unknown vector lies in; whereas in mixtures of linear regressions we observe the projection of a random unknown vector on the queried hyperplane. The primary step in recovering the unknown vectors from the mixture is to first identify the support of all the individual component vectors. In this work we study the number of measurements sufficient for recovering the supports of all the component vectors in mixture in both these models. provide algorithms that use a number of measurements polynomial in k, log and quasi-polynomia in l, to recover the support of all the unknown vectors the mixture with high probability when each individual component is k-sparse n-dimensional vector.
Introduction
In the support recovery problem, widely studied in the literature of compressed sensing [6, 2, 35]. the objective is to recover the support (positions of nonzero coordinates) of a sparse vector from minimal number of (noisy) linear measurements. The support recovery problem also extensively studied under the 1-bit compressed sensing model where measurements are further quantized and just the signs of the linear measurements are provided [22, 24, 1].
In a recent line of work that started with [46]. a generalization of the sparse recovery problem is considered [29, 31, 21, 11], where instead of one sparse vector, multiple unknown sparse vectors are to be recovered. However any attempt to obtain measurement (linear or 1-bit) from the vectors results in mixture model, where a vector from the unknown set is picked uniformly to generate the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

response. Due to the asynchronicity of the measurements, this set of problems pose fundamentally different challenges than recovery of single sparse vector.
This line of work also connects the mixture of simple learning models that have been studied extensively in the past few decades, with mixtures of linear regression model being more widely studied [13, 12, 23, 27, 39, 41, 44, 45, 48] than mixture of linear classifiers [43, 38]. Such mixture models, that assume the training data to come from multiple models, are good approximators of
function [4, 25J and have numerous applications in modeling heterogeneous settings such as machine translation [30]. behavioral health [15], medicine [5], object recognition [33] etc.
The mixture of sparse recovery models of [46] and followup works can be framed as a Mixture of Linear Classifiers (MLC) Mixture of Linear Regressions (MLR) problems. The statistical model in ML. is the following: there exists & unknown hyperplanes with normal vectors v1, v² v?,.... v and for particular feature vector, the label (response) is generated stochastically by selecting one of the unknown hyperplanes at random and then returning the side of the chosen hyperplane on which the feature vector lies. In MIR, the statistical model again assumes the presence of & unknown hyperplanes with normals v v² : v and for particular feature vector, the response is stochastically generated by selecting one of the unknown hyperplanes at random and then returning the projection of the feature vector to the chosen hyperplane. In order to make these models more general, we can assume that the responses are corrupted by noise. The overarching goal for both the MLR and MLC is to learn the & unknown hyperplanes as accurately as possible, using the least number of noisy responses. Sparsity, incorporated into the MLC and MLR problems, is also a common assumption that represents redundant features and lower dimensionality of the models (6,,6, 10].
In this work, we tackle the problem of support recovery of sparse vectors for both MLR and MLC model in the active query based setting of [46, 29, 31, 21J. Our goal is to recover the support of all the unknown sparse vectors (hyperplane normals) with minimum number of measurements.
1.1 Formal Problem Statement and Relevant Works
In both the problems below, let be set of unknown vectors v2, v2,..., ve E R such that ||'|| & for all i e [e] = 2
Mixtures of Sparse Linear Classifiers (MLC). Let sign : R + [-1.+1] be the sign function that takes real number and returns its sign. We consider MLC label queries O: : R. - [[1,+1] that takes as input a query vector E R and returns
sign((X, v)) (1 -2)
where v is sampled uniformly random from V and Z Ber(1)) the noise, is a Bernoulli random variable that is 1 with probability and 0 with probability 1- 17. In this problem, our objective is to recover the support of all the unknown vectors in using minimum number of label queries.
The only relevant work in this setting is [21] which provided results for both support recovery and approximate recovery of the unknown vectors. However, the results of [21] are valid only under the restrictive assumption that the support of any unknown vector is not contained within the union of the supports of the other unknown vectors.
In this work, we generalize the techniques of [21] for support recovery of the unknown vectors and get rid of the restrictive assumption. We further improve the generalized result in a wide regime by demonstrating new low-rank tensor decomposition based algorithm for support recovery.
Mixtures of Sparse Linear Regressions (MLR). In this setting, we have an MLR label map O T R that takes as input a query x E Ra and returns as output the quantity
(x, + 7
where v is sampled uniformly at random from V and Z ~ Ao o²) is zero-mean Gaussian random variable with variance o². For our MLR results to hold we further assume that the mini- mum magnitude of any non-zero entry of any unknown vector in V is known to be at least 8, i.e., mingeig minzeinlx [v']| 2 8.
Note that, because of the additive noise, a result for ML. setting cannot be transformed into a result in MLR setting (i.c., MLC response is not simple quantization of MLR).

---

It is possible to increase the & norm of the queries arbitrarily so that the noise becomes inconsequen- tial. To avoid this we use the following definition of signal noise ratio. Suppose the algorithm designs the 8th query vector by first choosing a distribution Q' and subsequently sampling query vector Q' The signal noise ratio is defined as follows:
Ex (x', v2)22
SNR max min JE(4]
EZ
Our objective in this setting is to recover the support of all unknown vectors v\, v², ,e,..,,'' while minimizing the number of queries for fixed SNR.
v² E R"
The most relevant works in this setting would be [46], [29] and [31], all of which were concerned with approximately recovering the k-sparse unknown vectors v², v² ...... vf i.e. computing estimates
V1, 42 .,....... ve such that for some precision parameter 7 > 0,
Viv f S 0()) for all i E [C]
for some permutation : [4] + [e]. While approximate recovery of vectors also be translated
into support recovery, the results of [46] and [29] are valid only under the restrictive assumption that the sparse vectors all belong to some scaled integer lattice. The results of [31] does not have any restriction, but holds only when = 2. However, note that in this special case i.e. when & = 2, [31] provides a query complexity guarantee that is linear in the sparsity k. On the other hand, our query complexity guarantees (see Section 2.3) have a polynomial dependence on k (with a larger degree) implying that in the regime when / and is large, the guarantees of [31] are better.
Here we provide results for support recovery of any number of unknown vectors that do not have any of the aforementioned restrictions and also have polynomial dependence on the noise variance, sparsity and near polynomial dependence on the number of unknown vectors.
1.2 Other Related Work
Learning the unknown vectors in the MLR setting is a generalization of the compressed sensing problem [8, 16] where the objective is to learn a single unknown k-sparse vector (E = 1) with minimum number of noisy linear measurements. Support recovery is well-studied area within this literature [6, 2, 35). Similarly, learning the unknown vectors the MLC setting is generalization of the 1-bit compressed sensing problem where the objective is to learn single unknown k-sparse vector (E = 1) with minimum number of linear measurements quantized to only 1-bit. Support recovery of the sparse vector from 1-bit measurements has also been widely studied [1. 22, 19, 24).
The major building block of one of our two algorithms is low-rank tensor decomposition also known as Canonical Polyadic (CP) decomposition. Tensor decomposition has been widely used in parameter estimation in mixture models and latent variable models. We refer the reader to [34] and the references therein for a detailed survey. Our other algorithm makes use of combinatorial structures such as a general class of Union Free Families (UFF), see, [42], to recover the support. UFFs have been previously used in [1] and [21] for support recovery in linear classifiers.
The rest of the paper is organized as follows. In Section 2, we gave the necessary backgrounds, and described our techniques and main results, namely, Theorems 1, 3, 4, and Corollary In Section we provided the detailed proofs of Theorem 1 (Section 3.1). Theorem (Section 3.2) and Theorem 4 (Section 3.3) while deferring the proof of Theorem 2 to Appendix D. In Appendix A, we provided the necessary background on families of sets and finally, in Appendix B, we gave the details of a Lemma that is an integral component of the proofs of our main Theorems.
Organization.
2 Our Techniques and Results
2.1 Preliminaries
Notations:
Let round IR- + Z denote function that returns the closest integer to given real
input. Let I, denote a length n vector of all I's. We will write [x]] to denote the set [1...., n) and let P((n)) be the power set of [r]]. For vector v E R", let v, denote its i-th coordinate for any i E [m]. We will use supp(v) S [ni] to denote the support of the vector v, i.e, the set of indices with non-zero
entries in v. We will abuse notations a bit, and also sometimes use supp(v) to denote the binary
3

---

indicator vector of length that takes 1 at index if and only v; # 0. For a vector v E R and subset S C [n| of indices, let vis E Rl denote the vector restricted to the indices in S. Finally, let f: P(nn)) x {0, 1 - {0, 1 be a function that takes binary vector S " [n] as input and returns another binary vector v' such that the indices of v corresponding to the the set 8 are flipped i.e. v - v, @ lif S and v = V; otherwise.
{0, 13"" and a subset
Tensor Decomposition: Consider a tensor A of order w E N,W w > 2 on R which is denoted by A E Rn & RR @ .... @ RR"h (w times). Let denote by Aig, where ,1, f2, ,ur E [r]] the element in A whose location along the jth dimension is ij i.e. there are ij elements along the jth dimension before A,, :2....... Notice that this indexing protocol uniquely determines the element within the tensor. For a detailed review of tensors, we defer the reader [28]. In this work, we are interested in low rank decomposition of tensors. A tensor A can be described as a rank-1 symmetric tensor if it can be expressed
A
Z z
lines
for some z E IR' i.e. A Ai,,i,,.... symmetric tensors is defined as rank R symmetric tensor. For such rank R tensor A provided as input, we are concerne with the problem of unique decomposition of A into sum of R rank-1 symmetric tensors, such decomposition is also known as a Canonical Polyadic (CP) decomposition. Below, we show a result due to [40] describing the sufficient conditions (Kruskal's result) for the unique CP decomposition of a rank R tensor A:
Z,,. A tensor A that can be expressed as a sum of R rank-1
Lemma (Unique CP decomposition [40]). Suppose A is the sum of R rank-one tensors i.e.
A= Dx
2z 3 Z
times
and further, the Kruskal Runk of the n x R matrix whose columns are formed by z ,?...., R is Then, if wJ > 2R + (w - 1), then the CP decomposition is unique and can recover the vectors z', zZ, ......... T up to permutations.
There exist many different techniques for CP decomposition of tensor but the most well-studied ones are Jennrich's 's Algorithm (see Section 3.3, [32]) and the Alternating Least Squares (ALS) algorithm [28]. Among these, Jennrich's 's algorithm (see Section E for more details) is efficient and recovers the latent rank-1 I tensors uniquely but it works only for tensors of order 3 when the underlying vectors z² z², ...., z are linearly independent (See Theorem 3.3.2, [32]); this is a stronger condition than what we obtain from Lemma 1 for w = 3. On the other hand, the ALS algorithm is an iterative algorithm which is easy to implement for tensors of any order but unfortunately. it takes many iterations to converge and furthermore, it is not guaranteed to converge to the correct solution. Jennrich's 's algorithm also has the additional advantage that it will throw an error if its sufficient condition for unique CP decomposition is not satisfied. This property will turn out to be useful for the problem that we study in this work. Finally, notice that if A is the weighted sum of R rank-1 1 tensors i.e.,
R
Ap
8
30
times
then we can rewrite A >E' y @ y 8 ... 8 y" where y \/ z" If [y") satisfies the conditions of Lemma and if it is known that (z" JR are binary vectors, then we can still recover z" by first computing y" and then taking its support for all E [R]. Subsequently, notice that we can also recover {\r J As we discussed, for tensors of order w 3, there is no known efficient algorithm that can recover the correct solution even if its existence and uniqueness is known. Due to this limitation, it was necessary in prior works using low rank decomposition of tensors that the unknown parameter vectors are linearly independent [9. 3] since tensors of order > could not be used. However, if it is known apriori that the vectors { are binary and the coefficients (A, }RR are positive integers bounded from above by some C > O, then we can exhaustively search over all possibilities (O(C2") of them) to find the unique decomposition even in higher order tensors. The set of possible solutions can be reduced significantly if the unknown vectors are known be sparse as is true in our setting.

---

2.2 Our Techniques
Recall that the set of unknown vectors is denoted by V v?...., vd). denote the support matrix corresponding to V where each column vector A, E {0, 10" represents the support of the ith unknown vector v*. For any ordered tuple C' c [n]] of indices, and any binary string a E (0, 1 ||(C), define occ(C, a) to be the set of unknown vectors whose corresponding supports have the substring a at positions indexed by i.e.,
Let A E {0, 10,
occ(C, = [v' E EV / supp(v') =
In order to describe our techniques and our results, we need to introduce three different properties of matrices and extend them to a of vectors by using their corresponding support matrix. The proofs of our main results follow from the guarantees of algorithms (Algorithm 1, Algorithm 2 and Algorithm 3) each of which leverage the aforementioned key properties of the unknown support matrix A. While explaining the intuition behind the introduced matrix properties, we will assume that all the unknown vectors in V have distinct supports for simplicity. However, this assumption is not necessary and the guarantees of all our algorithms hold even when the supports are not distinct albeit with slightly more involved arguments (see Section 3).
Definition 1 (p-identifiable), The ith column A; of a binary matrix A E {0, 10xxt with all distinct columns is called y-identifiable if there exists a set C [n] of at most p-indices and a binary string E {0, 1) such that A,ls a, and A,ls & a for all j +
A binary matrix A E {0, 13mxt with all distinct columns is called p-identifiable if there exists permutation o : [f] + [e] such that for all i [e], the sub-matrix A formed by deleting the columns indexed by the set (2)), - 1)} has at least one p-identifiable column.
Let V be set of unknown vectors in R", and A E {0, 1]nxe be its support matrix. Let B be the matrix obtained by deleting duplicate columns of A. The set V is called p-identifiable if B is p-identifiable.
Support matrix A is p-identifiable: Algorithm I uses the property that the support matrix A is p p-identifiable for some known p S log & (see Theorem 2) to recover the supports of all the unknown vectors. First, we briefly describe the support recovery algorithm of [21] where the authors crucially use the separability of supports of the unknown vectors to recover them. Their algorithm assumes that the support of each unknown vector contains a unique identifying index, i.e., for each unknown vector v e V. there exists a unique index E [n]] such that occ((i), 1) = {v). and hence (occ((i), 1) = 1. Observe that if (i))(()) 1)1 = 1, and (occ((i,)) j), (1, = 1 for some i * j. then it follows that both the indices j.j belong to the support of the same unknown vector. Therefore [21] are able to recover the supports of all the unknown vectors by computing (occ((i), 1) and (occ((i, j), (1. 1))] for all i.j E in]. The crux of their algorithm lies in computing all the n values of (occ((1), 1)), and (n values of Iocc ((, f), ()) using just pfly k) queries. We can generalize the support recovery technique of [21] by observing that if A is p-identifiable, then there exists at least one unknown vector v E V that has a unique sub-string of length at most p. Hence, there exists a unique set C' C [n]] and string a similar observation as before, occ((C (7}. (a. 1))l = 1 for some j E [n] C, we can certify that j E supp(v) and if occ((C U (5). 1))l 0, then j E supp(v). Hence can reconstruct the support of v and subsequently, we can update (occ(C, a)] + |cc((C, a) - 1 (supp(v), = al
{0, 13 satisfying |C' < p such that occ(C'U [5}. (a, 1)) {v}. By
for all sets C satisfying [C] S and all a E [0,1] Note that the updated occ values correspond to the support matrix A excluding the column corresponding to the support of v. From the definition of i-ieentifiable, we can recursively apply the same arguments as above and recover the support vectors one by one. The main technical challenge then lies in computing all the ((2Pn²) values (occ(C, a)l for every p and, p + 1-sized ordered tuples of indices and all a E 10, U (0, 1 (Lemma 2) using few queries.
Definition (ffp-independentt) A binary matrix A with all distinct columns is called tip-indepennent if there exists subset of rows that if complemented (changing 0 to 1 and 1 to 0) make all columns of A linearly independent.
Let V be set of unknown vectors in R., and A E {0, 1]axt be its support mairix. Let B be the matrix obtained by deleting duplicate columns of A. The set y has iip-inndeeeneett supports if B is flip-independent.
5

---

Support matrix is flip-independent: Algorithm 2 uses the property that the support matrix A dip-independent in order to recover the supports of the unknown vectors uniquely. As a pre- processing step, we identify the set 2 A Usepssupp(vv) that represents the union of support of the unknown vectors. Let us define 4t uu U {t} where t is any index that does not belong to U. This initial pre-processing step allows us to significantly reduce the computational complexity of this algorithm. Next, for each a E {0, 11s, Algorithm 2 recovers (occ( 22, 23), a) for every ordered tuple (f1, ig) Ut Using these recovered quantities, is possible to construct the tensors
A= = -E [(F,,suppyy) @ f(F, supp(v")) @ f(F, supp(v")) iE(e]
for every subset F. C Ut. Since the matrix A is flip-independent, we know that there exists at 4t such that the vectors {f(F" supp(""))") are linearly independent. From Lemma 1, we know that by a CP decomposition of A we can uniquely recover the vectors supp((")))
least one subset F S
since the set F is known, flipping all indices corresponding to F However, a remaining challenge is to correctly identify a set Ft. Interestingly, Jennrich's 's algorithm (see Algorithm 8 in Appendix E) throws an error if the tensor A under consideration does not satisfy the uniqueness conditions for CP decomposition i.e. the underlying unknown vectors {[FF, supp(v"))] are not linearly independent. Therefore Algorithm 2 is guaranteed to uniquely recover the supports of the unknown vectors.
recover all the vectors (supp(v")) by
Definition 3 (Kruskal rank). The Kruskal rank of a matrix A is defined as the maximum number r such that any r columns of A are linearly independent.
Definition (r-Kruskal rank support). Let V be a set of & unknown vectors in I", and E {0,, 1]mxe be its support matrix. Let B be the matrix obtained by deleting duplicate columns of A. The set V has r-Kruskal rank support if B has Kruskal rank r.
Support matrix has Kruskal rank r: Algorithm 3 partially generalizes the flip-independence property by constructing higher order tensors. Again, as a pre-processing step, we identify the set u e Uie(gsupp(vv) that represents the union of support of the unknown vectors. Note that [2]] s tk since each unknown vector is k-sparse. Since Jennrich's 's algorithm is not applicable for tensors of order more than 3, we will simply search over all (((k))a)) possibilities order to compute the unique CP decomposition of an input tensor. Unfortunately though, if the sufficiency conditions (Lemma 1) for unique CP decomposition is not met, there can be multiple solutions and we will not be able to detect the correct one. This is the reason why it is not possible completely generalize Algorithm 2 by constructing multiple tensors of higher order. To circumvent this issue, Algorithm constructs only a single tensor A of rank l and order w = [ 1 by setting its (i1,.... , )-th entry to locc((e ((i......... iw),, 1 for every ordered tuple (i1..... (w) E [n]". By using Theorem 1, the recovery of the supports of the unknown vectors via brute force CP decomposition of the constructed tensor is unique if the support matrix has Kruskal rank r.
All the above described algorithms require Lemma 2 that for any > 1 computes (occ(C,a) for every s-sized ordered tuple of indices C. and any E f0, 1] using few label queries. The key technical ingredient in Lemma 2 is to estimate nzcount(x) the number of unknown vectors that have a non-zero inner product with x. Note that even this simple task is non-trivial in the mixture model and more so with noisy label queries.
2.3 Our Results
The MLC results below explicitly show the scaling with the noise, whereas all of the MLR query results below are valid with
SNR o max
aE|e]
In our first result, we recover the support of the unknown vectors with small number of label queries provided the support matrix V is p-identifiable.
Theorem 1. Let V be set of & unknown vectors in R" such that V is p-indentifiable. Then, Algo- rithm I recovers the support of all the unknown vectors in V with probability at least 1 - 1 (1/n) using either (1) ( (Ekyp++ log(fkn) log
MLC queries or (2) O (( (og(k)))))))
(1-2n)²
MLR queries.

---

In fact, all binary matrices with distinct columns are p-identifiable for some sufficiently large p. Theorem 2. Any x e, (with binary matrix with all distinct columns is p-identifiable for some < log f.
Thus, we have the following corollary characterizing the unconditional worst-case guarantees for support recovery:
Corollary 1. Let V be a set of & unknown vectors in R Then, Algorithm 1 recovers the sup- port of all the unknown vectors in V with probability at least 1 (1/n) using either (1) O 8 (ER) log " 1o MLC queries (2) O(e e+2 log(Ekn) logn) MLR queries.
(1-27))*
Proof. The proof follows from the fact that any set V & unknown vectors in R must have p-identifiable supports for log f.
Under some assumptions on the unknown support, e.g. e.g. fiffip-indeeendence, we have better results.
Theorem 3. Let V be a set of i unknown vectors in R" such that V is flip-independent. Then, Algorithum recovers the support of all the unknown vectors in V with probability least 1
O (1 (n) using either (1) O (E8) log log
MLC queries or (2) ((k) log((kn)) logn)
(1))
MLR queries.
We can also leverage the property of small Kruskal rank of the support matrix to show:
Theorem 4. Let V be set of unknown vectors in RR that has v- y-Kruskal rank support with 2 2. w 7. Then, Algorithm 3 recovers the support of all the unknown vectors in with
probability at least O (1/n) using either (1) O ((k))=+ log(Eke)) log
MLC queries or (2)
(1-29)²
( log MLR queries.
Discussion Matrix Properties: Note that p-identifiability (Definition 1) is a generalization of the separability conditions outlined by [21] for support recovery. This generalization allows us to recover the supports of all the unknown vectors in the worst-case without any assumplions (Corollary 1). The flp-indeppendence (Definition 2) and r-Kruskal rank support (Definition 4) properties are used the desso-ddcompoosttion based support recovery algorithms and follow naturally from Lemma 1. The flip-independence assumption is quite weak, however there do exist binary matrices that are not flip independent. For example
0
1
0
17
0
0
M =
1
1
1
1
not flip independent. The Krruss rank support condition generalizes linear independence conditions considered in previous mixture model studies such [45]. Note that this condition is always satisfied by the support vectors for some 2 2. Essentially, we 1) provide algorithms for support recovery without any assumptions, 2) and also provide significantly better guarantees under extremely mild assumptions.
Although we have not optimized the run- uuntimme of our algorithms in this work, we report the relevant computational complexities below:
Remark (Computational Complexity). Note that Algorithm 1 has a computational complexity that polynomial the sparsity k, dimension n. and scales as O(E)) where p S log f. On the other hand Algorithms 2, 3 has a computational complexity that scales exponentially with k, E while remaining polynomial the dimension n. For the special case when the support matrix is known be full rank, Algorithmm with w = 3 is polynomial in all parameters (by using Algorithm 8 for the CP decomposition.)
3 Detailed Proofs and Algorithms
Recall the definition of occ(C, the number of unknown vectors whose supports have E {0, He as substring coordinates C C [n]. First, we observe that for any set S {0, 1),, we can compute Jocc(C, a)] for all O(n²) subsets of indices C' c. [ra] and a T using few MLC MLR queries.
7

---

Lemma 2. Let T C {0,1]* be any set of binary vectors of length There exists an algorithm to compute locc C, a)) for all C [n] of size s, and all a E T with probability at least 1/n using either ( (Ak) (0k))+1 log( (km) nggn/(1 - 2n)²) MLC queries or (((()))+
(Ok)o+1 log(fkn) log n)
MLR queries.
Lemma22 2 (proved in Section B) is an integral and non-trivial component of the proofs of all our main Theorems. In each of the sub-sections below, we go through each of them.
3.1 Recovery of p-identifiable support matrix
In this section we present an algorithm for support recovery of all the & unknown vectors V = (v'..... v'} when V is p-identifiable. In particular, we show that if V is p-identifiable, then computing /cc(C,a) a) for every subset of p and p + indices is sufficient to recover the supports.
Proof of Theorem I. The proof follows from the observation that for any subset p indices C' C [n]] index E [n] \ C' and {0, 1I", |occ(C, a)] locc(C' u [ī}, (a, 1))l + locc(C U (i), (a. 0))
Therefore if one of the terms in the RHS is 0 for all j E [m] \ C, then all the vectors in (C, share the same support.
Also, if some two vectors u, V occ(C, a) do not have the same support, then there will exist at least one index j E [n] \ C such that u E (cc(C U (i), (a, 1)) and v E occ(C U {i}, (a, 0)) or the other way round, and therefore |occ(C {j}, (a, 1))l & {0. (occ(C, a))3. Algorithm 1 precisely checks for this condition. The existence of some vector v E V (p-identifiable column), a subset of indices C' C [n] of size p. and binary sub-string b E (0, 1 follows from the fact that is p-identifiable. Let us denote the subset of unknown vectors with distinct support in V by V
Once we recover the p-identifiable column of V1, we mark it as u² and remove it from the set (if there are multiple y-identifiable columns, we arbitrarily choose one of them). Subsequently, we can modify the occ(-)] values for all C [m]. E {p.p + 1} and E {0,1)* U {0, (0,1) follows:
locc? (S. t) A occ((S, t)] - (ccc(C, b) x 1 [ssupp(ul) (u )|s = t).
(2)
Notice that, Equation 2 computes |occ" t) l(v E D2 ssupp(v))s by deleting all copies of u' from V. Since V is p-identifiable, there exists p-identifiaalee column in 1 \ {u') as well which we can recover. More generally for > 2, if u is the p-identifiable column with the unique binary sub-string ba-1 corresponding to the set of indices Ca we will have for all S S [m], [S| {p.p- + 1} and t E {0, 10.1 (0,
t where y is formed
(S, t) _ occ -C,
10oc--((90-1 (C9-1,bb-3) b x ([supp(u>-1) =t
implying (S, [[v E 1o supp( v')ls | where V is formed deleting all copies of u', u² ...., u from V. Applying these steps recursively and repeatedly using the property that V is p-identifiabll, we can recover all the support of all the vectors present in V.
Algorithm/ requires the values of |occ(C: a)). and locc(C, a)] for every p and + 1 sized subset of
indices C, Ò C [n], and every a E (0, 1)", à E {0. 1]p-1. Using Lemma 2, we can compute all these values using O ((kk)))) log(Ekn) log n/ 2n) MLC queries or (((((k)) log(Ekn) logn)
MLR queries with probability at least 1 - On"
3.2 Recovery of flip-independent support matrix
In this section, present an algorithm that recovers the support of all the unknown vectors in V provided V is flip-independent.
Proof of Theorem 3. The query complexity of the algorithm follows from Lemma 2. For any subset C of 3 indices, with probability - O(1/n), we can compute (occ(C,,)] using (EK)))) log(fkn) logn/(1 - 22)))) MLC queries O (ek) logn) MLR queries.
For every subset
S U' we construct the tensor AF as follows:
A (
locc((é,, i2, is). (o.1 0.2, az))),, for all (2,,2, is) is) wise. We then run Jenerich's 's algorithm each AF, Observe that for any binary vector b (0, 13".
[n] where aiy Of in F and 1 other-
8

---

end for Algorithm 1 RECOVER P-IDENTIFIABLE SUPPORTS
Require: |occ(C, a)| for every C' [n]. [C| t, te {p.p 1}, and every {0, 13 {0, 1,
1: Set count = 1, 1.
2: while count < do
3: if [occ(C,, a)l we and lcc((C U (a. 1))1 E {0, w) for all E [n]] \ C then
4: Set supp (u')lc a
5: For every j E [r] \ C, set supp(uu)) = where occ(C' [j), (a, b]) = w.
6: Set Multiplicity
7:
For all E {0.1)* u (0, 13 SS [x] such that |S| E (p.p + 1), update (oc((S, t)] - occ(S (, t) (occ(C, x (supp(u') u Is t)
8:
count = count + w.
9: i
10: end if
11:
end while
12:
Return Multiplicity' copies of supp(u') for all j <
Algorithm RECOVER FLIP-INDEPENDENT SUPPORTS
Require: |occ(C, a for every C' C [n]] such that |C] = 3, and all a E {0, 1}3. locc(i, 1) for all
iE (n].
1: Set li {i [n] locc(i, (i, 1)1 * 0} and U' = u where / E [ni] V.
2: for each F U' do
3: Construct tensor A as follows:
4: for every (i1, i3) E [n] 3 do
5: Set A (sndda lccc ( i2, ia), (an d:2, a.))),
where Oij = if F and otherwise.
6: end for
7:
if Jenerich(AA)) (Algorithm 8 with input A²) succeeds: then
8: Let A = ΣΣ A. a² @ a' the tensor decomposition A such that a E (0, 1)
9: For all E [R], modify a" by flipping entries in
10: Return A; columns with modified a', vi (R).
break
12: end if
13:
the (i1, 12, ia)-th entry of the rank-1 tensor b ② b 2 is if bi, = bi =b, bi = 1, and 0 otherwise. Therefore, the tensor _ can be decomposed as A DB X, a & a', where the vectors a {0, 1)" i R are the support vectors (of the R distinct unknown vectors) that are flipped at indices in F. with multiplicity A;-
Now if the support matrix of the unknown vectors is flip-independent, then there exists subset of rows indexed by some F S [n] (and furthermore, J C 2L') such that flipping the entries those rows results in modified support matrix with all its distinct columns being linearly independent.
Since all the zero rows of the support matrix A are linearly independent (flipped not), we can search for F as subset of L'. Since, [4'| < lk + 1, this step improves the search space for F* from (22)) to (22k).
Therefore, Jennrich's algorithm on input FF is guaranteed to succeed and returns the decomposition AA = > A,a @ a' @ as the sum of R rank-one tensors, where, a' {0, 1)", E [R] are modified support vectors (with multiplicity X₃). Subsequently, we can again flip the entries of the recovered vectors indexed by F to return the original support vectors.

---

Algorithm 3 RECOVER r- R-KRUSKAL RANK SUPPORTS
1: Let w be smallest integer such that w (r- 1) 2 2 1.
Require: locc(C. C, 1w) for every C [n] with [C] = w. Jocc(i, 1)1 for E [n].
2: Set & {i E [n] : occc(i, 1)] A 0}.
3: Construct tensor A as follows:
4: for every (f1....,,u) E [n| do
5: Set (i occ (1....., , Iw))
6: end for
7: for every (b' b be...,,bi b¹) E [0,1)* satisfying supp(b') C u do
8: if Σ iim b' @ b.... bc (w times) then
9:
Set (b², b ..., bd) to be the CP decomposition of A and Break
...,,b))
10: end if
end for
12:
Return CP decomposition of A
3.3 Recovery of r-Kruskal rank supports
In this section, present an algorithm that recovers the support of all the l unuknown vectors provided they have r- Kruskkll rank supports. Recall that for any set of w indices C' C [nt]. occ(C, 1w) denotes the set of unknown vectors that supported on all indices in C.
Proof of Theorem 4. To recover the supports we first construct the following order w tensor: (()......w.) .c.. (w), 1w)l. for (ww) [n]"". Observe that the tensor AA can be written the sum of l' (L' E) rank one tensors
A
X supppvv) 8... & supp(v')
(3)
wetimes
where v 2 ...., ve are the unknown vectors with distinct supports in V with X' being the mul- tiplicity of supp(v"). Since the support matrix A of V has r-Kruskal rank, for any w such that (r (r-1) > 28- 1, the decomposition of Eq. (3) is unique (Lemma 1). Notice that by pre- processing step, we compute 21 ê {i E [n]: |occ(i, 1) A 0} be the union of the supports of the unknown vectors. Since we know that the underlying vectors of the tensor that we construct are binary, we can simply search exhaustively over all the possibilities (O((Ek)( of them (Steps 7-10) to find the unique CP decomposition of the tensor A. For the special case when w = 3, Jennrich's 's algorithm (Algorithm 8) can be used efficiently compute the unique CP decomposition of the tensor A.
Algorithm 3 needs know the values of locc(C, 1w) for every C C [n]. such that |C| w. Using Lemma 2, these can be computed using ( ((()))))=+ w+1 log( (kn) log n/(1 - 2n)²) MLC queries or ( (Ek)) log(Ckn) log n) MLR queries with probability least 1 O(1nn)
10

---

Acknowledgements:
This work is supported in part by NSF awards 2133484, 2127929, and
1934846.
References
[1] Jayadev Acharya, Arna Bhattacharyya, and Pritish Kamath. Improved bounds for universal one-bit compressive sensing. In 20/7 IEEE International Symposium on Information Theory (ISTT), pages 2353-2357, IEEE, 2017.
[2] Shuchin Aeron, Venkatesh Saligrama, and Manqi Zhao. Information theoretic bounds for compressed sensing. IEEE Transactions on Information Theory, 56(10):5111-5130, 2010.
[3] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research, 2014.
[4] Christopher M Bishop. Latent variable models. In Learning in graphical models, pages 371-403 Springer, 1998.
[5] Ekin Blackwell, Carlos F Mendes De Leon, and Gregory E Miller. Applying mixed regression models to the analysis of mepaated-measures data in psychosomatic medicine. Psychosomatic medicine, 68(6))870-878, 2006.
[6] Thomas Blumensath and Mike Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 27(3):265-22 2744, 2009.
[7] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
[8] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489-509, 2006.
[9] Arun Tejasvi Chaganty and Percy Liang. Spectral experts for estimating mixtures of linear regressions. In International Conference on Machine Learning, pages 1040-1048, 2013.
[10] Antoni B Chan, Nuno Vasconcelos, and Gert RG Lanckriet. Direct convex relaxations of sparse In Proceedings of the 24th international conference Machine learning, pages 145-153, 2007.
[11] Yanxi Chen, Cong Ma, H Vincent Poor, and Yuxin Chen. Learning mixtures of low-rank models. arXiv preprint arXiv:2009. 2020.
[12] 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.
[13] Richard D De Veaux. Mixtures of linear regressions. Computational Statistics & Data Analysis, 8(3):227-245, 1989.
[14] Ronald De Wolf. Efficient data structures from unionfree families of sets, 2012.
[15] Partha Deb and Ann M Holmes. Estimates of use and costs of behavioural health care: comparison of standard and finite mixture models. Health economics, 96):475-489, 2000.
[16] DL Donoho. Compressed sensing, IEEE Transactions on Information Theory, 1284):1289-1306
2006.
[17] Arkadií G D'yachkov, IV Vorobyev. NA Polyanskii, and V Yu Shchukin. Bounds on the rate of superimposed codes. In 20/4 IEEE International Symposium on Information Theory, pages 2341-2345. IEEE, 2014.
[18] Paul Erdös, Peter Frankl, and Zoltán Füredi. Families of finite sets in which no set covered by the union ofr others. Israel Journal of Mathematics, 51(1-2):79-89, 1985.
11

---

[19] 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.
[20] Zoltán Füredi. On r-cover-free families. Journal of Combinatorial Theory, Series A, 73(1):172- 173, 1996.
[21] Venkata Gandikota, Arya Mazumdar, and Soumyabrata Pal. Recovery of sparse linear classifiers from mixture of responses. In Advances in Neural Information Processing Systems 33: NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[22] Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya Nori. One-bit compressed sensing: Provable support and vector recovery. International Conference on Machine Learning, pages 154-162, 2013.
[23] Mian Huang, Runze Li, and Shaoli Wang. Nonparametric mixture of regression models. Journal of the American Statistical Association, 1084543), 2013.
[24] 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.
[25] Michael Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm. Neural computation, 1(1):181-214 1994.
[26] William Kautz and Roy Singleton. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory, 10(4):363-377 1964.
[27] Abbas Khalili and Jiahua Chen. Variable selection finite mixture of regression models. Journal of the american Statistical association, 1025479) 2007.
[28] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455-55 (1000,55-500,,10 2009.
[29] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Sample complexity of learning mixture of sparse linear regressions. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[30] Percy Liang, Alexandre Bouchard-Côre -ôtt, Dan Klein, and Ben Taskar. An end-to-end discrimina- tive approach to machine translation. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, pages 761-768. Association for Computational Linguistics, 2006.
[31] Arya Mazumdar and Soumyabrata Pal. Recovery of sparse signals from mixture of linear samples. In International Conference on Machine Learning (ICML), 2020.
[32] Ankur Moitra. Algorithmic aspects of machine learning. Lecture notes, 2014.
[33] Ariadna Quattoni, Michael Collins, and Trevor Darrell. Conditional random fields for object recognition. In Advances in neural information processing systems, pages 1097-1 104, 2005.
[34] Stephan Rabanser, Oleksandr Shchur, and Stephan Günnemann. Introduction to tensor de- compositions and their applications in machine learning. arXiv preprint 1rXiv:1711.107. 2017.
[35] Galen Reeves and Michael Gastpar. A note on optimal support recovery in compressed sensing. In 2009 Conference Record of the Forty-Third Asilomar Conference Signals, Systems and Computers, pages 1576-1580. IEEE, 2009.
[36] Galen Reeves, Jiaming Xu, and Ilias Zadik. The all-or-nothing phenomenon in sparse linear regression. In Conference on Learning Theory, pages 2652-2663. PMLR, 2019.
[37] Miklós Ruszinkó. On the upper bound of the size of the r-cover-free families. Journal of Combinatorial Theory, Series A, 66(2):302-310, 1994.
12

---

[38] Hamie Sedghi, Majid Janzamin, and Anima Anandkumar. Provable tensor methods for learning mixtures generalized linear models. In Artificial Intelligence and Statistics, pages 1223-1231. PMLR, 2016.
[39] Yanyao Shen and Sujay Sanghavi. Iterative least trimmed squares for mixed linear regression. arXiv preprint 1XX.::902.006533. 2019.
[40] Nicholas D Sidiropoulos and Rasmus Bro. On the uniqueness of multilinear decomposition of n-way arrays. Journal of Chemometrics: A Journal of the Chemometrics Sociery, 14(3):229-25) 2000.
[41] Weixing Song, Weixin Yao, and Yanru Xing. Robust mixture regression model fitting by laplace distribution. Computational Statistics & Data Analysis, 71:128-137, 2014.
[42] Douglas R Stinson and Ruizhong Wei. Generalized cover-free families. Discrete Mathematics, (193)4):463 2004.
[43] Yuekai Sun, Stratis Ioannidis, and Andrea Montanari. Learning mixtures of linear classifiers. In ICML, pages 721-729, 2014.
[44] Taiyao Wang and Ioannis Ch Paschalidis. Convergence of parameter estimates for regularized mixed linear regression models. arXiv preprint (rXiv:1903.09253: 09235, 2019.
[45] Xinyang Yi, Constantine Caramanis, and Sujay Sanghavi. Solving mixture of many ran- dom linear equations by tensor decomposition and alternating minimization. arXiv preprint 1:Xv::/608.05749 2016.
[46] Dong Yin, Ramtin Pedarsani, Yudong Chen, and Kannan Ramehandran. Learning mixtures of sparse linear regressions using sparse graph codes. IEEE Transactions on Information Theory, 650))1140-1151, 2019.
[47] Yuchen Zhang, Martin Wainwright, and Michael Jordan. Lower bounds on the performance of polynomial-tims algorithms for sparse linear regression. In Conference on Learning Theory, pages 921-948. PMLR, 2014.
[48] Hong-Tu Tu Zhu and Heping Zhang. Hypothesis testing in mixture regression models. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 66(1):3-16, 2004.
13


Reviews:
[{"review_id": "u1vuIIAw4ch", "reviewer": "Reviewer_WFKv", "summary": "The paper considers the support recovery of sparse vectors from linear mixtures. They extend the results from prior works by relaxing some assumptions and provide support recovery using a low-rank tensor decomposition.", "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": "The paper is well-organized and written well. Related works is properly discussed and the authors explained well how their work differs from prior works. The paper studies the support recovery of sparse vectors from linear mixtures. As also pointed out by the authors, prior works have studied the approximate recovery of the sparse signals in a similar problem. This work mainly extends [29], relaxes some assumptions, and focuses on support recovery. Hence, the paper is incremental and lack originality. Sufficient discussion and remarks are provided on the derived theorems.\n\nIn addition, although the paper includes theoretical results on the problem discussed, it ends with no conclusion section and lacks numerical results supporting their theorem. In the absence of conclusion and no numerical experiments to verify their theorem, the papers does not meet the standards for NeurIPS publication.\n\nBelow are my further comments:\n\n- Although mentioned in the related works section, please explain which techniques used in this paper differ from those in [27, 29, 44]. This can help the authors to show the originality of the work in their method and techniques.\n\n- It is known that compressed sensing has many real-world application in radar, MRI, etc. What are the applications of the sparse linear mixture model? An experiment section with baseline comparison is needed to show the performance of the proposed algorithms.\n\n- Include numerical analysis. For example, phase transition curve on support recovery as the number of measurements and sparsity level changes.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- No negative impact is discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "TsObEUTF7HS", "reviewer": "Reviewer_8hHY", "summary": "This paper considers a support-recovery problem for a mixture of sparse linear classifier and regressions with $l \\ge 2$ number of components in the active-learning setting, i.e., where we can design input-vectors (or queries, as few as possible). For sparse linear classifiers, unlike in previous work [19] where supports of any two unknown vectors are disjoint, the authors consider a few milder assumptions on the support (Definition 1 and 2). For sparse linear regressions, they do not impose target vectors to be on some scaled integer lattice [27, 44] (but instead we need minimum magnitude $\\delta > 0$ for any non-zero entry, and some high SNR condition). \n\nIn order to recover all supports, three assumptions are considered for the support-matrix: (1) p-identifiable, if some size $p$ subset of support locations uniquely decides an unknown vector, then the authors can devise some combinatorial approach extending [19], (2) flip-independent, which essentially is required for some 3rd-order (support) tensor uniquely decomposable, (3) more general case where we deal with higher-order (support) tensor decomposition which cannot be done in polynomial-time in general but for full-rank 3rd order tensors. \n\nThe heart of the proposed algorithms for all three cases is to compute $|occ(C,a) := \\{v \\in \\mathcal{V} | \\ supp(v)|_C = a \\}|$ for all possible combination of $C$ and $a$ of a fixed length $s \\ge 1$ (Lemma 2). It seems quite non-trivial to compute all these $\\Omega(n^s)$ quantities using only $O(log n)$-queries. Equipped with this powerful lemma, subsequent procedures seem to be nice combinatorial arguments adjusted to different assumptions. Overall algorithms and proofs are quite non-trivial. ", "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": "The paper is well-written: problem statement is clear, comparison to previous work is well described, background knowledge is kindly introduced whenever necessary, and the main results are easy to catch. Here, I have to admit that I am not very familiar with union-free family or cover-free family literature, hence I cannot fully appreciate Lemma 2 which seems to be the core of all proposed algorithms. I instead raise some concerns from different aspects:\n\n- Why do you consider only to recover the supports (in [29], it was possible to recover all regression vectors although with some assumptions). Are there any fundamental challenges?\n\n- Related to the previous one, for MLR, I wonder if a naive idea can work: lets say we just use Gaussian input design $x \\sim \\mathcal{N}(0,I)$. Then for each coordinate $i \\in [n]$, just estimate $\\mathbb{E} [y^2 x_i^2]$ where $y$ is a response for the query $x$. This expectation gives (constant + $\\frac{1}{l} \\sum_{j=1}^l |v_{j}^i|^2$), and all coordinates $i \\in [n]$ can be estimated with $O(poly(k,l) log n)$ samples. What would be the drawback of this approach, and what is the merit of your algorithm?\n\n- Again for MLR, an interesting aspect of [29] was that the query complexity was linear in sparsity $k$. With passive Gaussian design, a statistical-query lower bound $\\Omega(k^2)$ is known (even for $l = 2$) (e.g., Brennan & Bresler 2020), and getting a $O(k^2)$ upper-bound is relatively easy for $l = 2$ case. So if much higher order in $k$ is allowed, why shouldn't we just work with passive Gaussian input design?\n\n- Flip-independent - this assumption seems very tricky. How natural is this assumption (e.g., would there be more easy-to-understand assumption that can be implied by this?) \n\n\n\n\nOn Complexity Results\n\n- For MLR, a recent result by (Diakonikolas & Kane 2021) gives a quasi-polynomial time complexity result. Could you compare your result to them?\n\n- Is there any fundamental limits (e.g., exponential lower bound) for the general case (Kruskal-rank, without full-rank 3rd-order tensor)?\n\n\n\nSome other comments\n\n- It would have been much helpful if more space has been allocated to explain (in high-level) how to compute $|occ(C,a)|$. Has this or some similar idea been appeared before somewhere? If so, reference to such literature would be nice.\n\n- Line 263: \"we have better results\" - Are the results for Algorithm 1 and 2 comparable? In other words, is flip-independence a special case of p-identifiability?\n\n- Line 595: \"Moreover, SNR = ...\" - what does this mean?\n\n\n\nReferences \n\n- M. Brennan and G. Bresler, Reducibility and statistical-computational gaps from secret leakage, 2020.\n\n- I. Diakonikolas and D.M. Kane, Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models, 2020.\n\n\n\n\n\n\n\n\n\n==============================================\n\nPost-Rebuttal: Thanks to the authors for a thoughtful response. It seems more clear to me now what the motivation is - more unified approach for mixture of linear models (MLC, MLR).\n\nAt this point, I still wonder how significant the results are for MLR, but for MLC it seems interesting. If there were more known results for solving MLC with passive input design, it would have been easier to appreciate this work further.\n\nCurrently, the focus of the paper is mostly on discussing conditions. But I am not sure whether they are interesting conditions on their own - maybe why other reviewers felt that some experiments seem necessary. Nevertheless, I think there are some good ideas and results in Lemma 2 + several other places in supplementary materials. I increased my score accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall narrative of the paper is \"we just solved a problem under this and that assumptions\", but it would be nicer to see what can be said of learning mixture models which have been extensively studied, e.g., what main results can imply for them, why active-learning setting should be of interest, and so on. Also, I would like to hear what can be possible next steps. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Q7s0vHz0XB", "reviewer": "Reviewer_riqJ", "summary": "This work studies support recovery of a collection of multiple, unknown sparse vectors using a small number of noisy linear or 1-bit observations where the observations are constructed from random mixtures of the unknown sparse vectors. In other words, for each measurement, one of the multiple, unknown sparse vectors is chosen uniformly at random to generate the response and we aim to learn the support of all of these unknown vectors from the mixed measurements using the least amount of measurements as possible. In particular, the work considers sample complexity of recovery in both models and provides efficient algorithms to perform the recovery. Previous work in the area considered either approximate recovery under restrictive assumptions or support recovery only for the case where there are \\ell = 2 unknown sparse vectors (of course, the \\ell = 1 case has been studied extensively). This work considers support recovery for \\ell >= 2 unknown sparse vectors.", "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": "I believe that the problem studied in this work is nicely formulated and introduced that is of relevance to the NeurIPs community. I also believe the work to be theoretically precise, but at some times the writing seems to be a bit terse, obviously due in some part to tight page limits. I think the authors could do a bit of a better job with the organization and presentation of the assumptions, algorithms, and main results. For example, while I recognize that the authors want to give some intuition to the assumptions in Section 2.2, it's somehow odd to read high level overviews of the algorithms there when the algorithms aren't formally described until much later in the paper. My main concern is about the significance of the research: while the work generalizes the assumptions made in previous works studying the problem like [19] or [29], it's not clear to me that this line of work has found many applications nor is it clear that the generalizations presented here will help it find new applications. Perhaps the authors could discuss a bit about how their conceptual tools or novel proof techniques could aide future research in related problems.\n\nSome typos:\n-- I found equation (1) confusing. What does it mean to minimize over \\ell, when \\ell is the total number of unknown v vectors? Perhaps minimizing over j \\in [\\ell] would be more clear.\n-- Line 88: \"Here we provide results for support recovery... that DO not have...\"\n-- Line 122: \"Such that the indices of v corresponding ... ARE flipped\"\n-- Line 130: should it be \\mathcal{A}_{i1,..., iw} = \\Prod_{j=1}^w z_{ij + 1} or are vectors in R^n also indexed from 0 to n-1?", "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": "2"}, "extra_text": {}}, {"review_id": "21-glpD4uWg", "reviewer": "Reviewer_LAr2", "summary": "The paper considers support recovery of multiple sparse vectors with the same sparsity level from a mixture of linear measurements in the tensor setting with CP decomposition. Specifically, several algorithms for various types of support matrix, including p-identifiable, flip-independent and r-Kruskal rank support matrices, are proposed to solve the problem, together with computational cost analysis in terms of mixture of sparse linear classifiers (MLC) and mixture of sparse linear regressions (MLR). ", "questions": "", "limitations": "", "rating": 6, "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 work that uses the tensor framework to recover multiple sparse signals with the same sparsity level from a mixture of linear measurements is interesting. In particular, support recovery is embedded into the MLC and MLR models. However, the motivations and contributions of the proposed algorithms, especially the use of low CP-rank assumption, are not fully clear, which could be highlighted. The title could be more specific about the tensor setting. Although theoretical success guarantees of the proposed algorithms are provided, numerical justifications are completely missing. The paper seems incomplete to some point. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumptions about the feasibility of the proposed algorithms should be justified in practice. Numerical implementation details and performance comparisons with the state of the arts should be provided to make this work more attractive. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes new algorithms for support recovery for mixtures of sparse linear regressions/classifiers. Recovery guarantees are obtained, which improve/generalize several previous results. However, the reviewers feel that the contributions are somewhat incremental given the existing work in [19,27,29,44]. The authors could also have done a better job motivating the problem setting and assumptions. It is currently clear if this results are of significance interest to the NeurIPS community, especially as the paper has focused on theory without numerical experiments for their new algorithms.
Decision: Accept (Poster)