Support Recovery of Sparse Signals from a Mixture of Linear Measurements
Year: 2022

Abstract:
Recovery of support of a sparse vector from simple measurements is a widelystudied 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 `, to recover the support of all the ` unknown vectors in the mixture with high probability when each individual component is a k-sparse n-dimensional vector.

heading: 1 Introduction
text: 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 is 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 a measurement (linear or 1-bit) from the vectors results in a mixture model, where a vector from the unknown set is picked uniformly to generate the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
response. Due to the asynchronicity of the measurements, this set of problems pose fundamentally different challenges than recovery of a 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 a function [4, 25] 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) or a Mixture of Linear Regressions (MLR) problems. The statistical model in MLC is the following: there exists ` unknown hyperplanes with normal vectors v1,v2, . . . ,v` and for a 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 MLR, the statistical model again assumes the presence of ` unknown hyperplanes with normals v1,v2, . . . ,v` and for a 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 [47, 36, 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, 21]. Our goal is to recover the support of all the unknown sparse vectors (hyperplane normals) with minimum number of measurements.

heading: 1.1 Formal Problem Statement and Relevant Works
text: In both the problems below, let V be a set of ` unknown vectors v1,v2, . . . ,v` 2 Rn such that vi 0  k for all i 2 [`] ⌘ {1, 2, . . . , `}.
Mixtures of Sparse Linear Classifiers (MLC). Let sign : R ! { 1,+1} be the sign function that takes a real number and returns its sign. We consider MLC label queries O : Rn ! { 1,+1} that takes as input a query vector x 2 Rn and returns
sign(hx,vi) · (1 2Z) where v is sampled uniformly at random from V and Z ⇠ Ber(⌘), the noise, is a Bernoulli random variable that is 1 with probability ⌘ and 0 with probability 1 ⌘. In this problem, our objective is to recover the support of all the unknown vectors in V 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 a 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 : Rn ! R that takes as input a query x 2 Rn and returns as output the quantity
hx,vi+ Z where v is sampled uniformly at random from V and Z ⇠ N (0, 2) is a zero-mean Gaussian random variable with variance 2. For our MLR results to hold we further assume that the minimum magnitude of any non-zero entry of any unknown vector in V is known to be at least , i.e., mini2[`] minj2[n]:vij 6=0 |v i j | .
Note that, because of the additive noise, a result for MLC setting cannot be transformed into a result in MLR setting (i.e., MLC response is not simple quantization of MLR).
It is possible to increase the `2 norm of the queries arbitrarily so that the noise becomes inconsequential. To avoid this we use the following definition of signal to noise ratio. Suppose the algorithm designs the ith query vector by first choosing a distribution Qi and subsequently sampling a query vector xi ⇠ Qi. The signal to noise ratio is defined as follows:
SNR = max i min j2[`]
Exi⇠Qi |hxi,vji|2
EZ2 . (1)
Our objective in this setting is to recover the support of all unknown vectors v1,v2, . . . ,v` 2 Rn while minimizing the number of queries for a fixed SNR.
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 v1,v2, . . . ,v` i.e. computing estimates v̂1, v̂2, . . . , v̂` such that for some precision parameter > 0,
kvi v̂ (i)k2  O( ) for all i 2 [`] for some permutation : [`] ! [`]. While approximate recovery of vectors can 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 it 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 ` = 2 and k 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 a polynomial dependence on the noise variance, sparsity and a near polynomial dependence on the number of unknown vectors.

heading: 1.2 Other Related Work
text: 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 (` = 1) with minimum number of noisy linear measurements. Support recovery is a well-studied area within this literature [6, 2, 35]. Similarly, learning the unknown vectors in the MLC setting is a generalization of the 1-bit compressed sensing problem where the objective is to learn a single unknown k-sparse vector (` = 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.
Organization. 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 1. In Section 3, we provided the detailed proofs of Theorem 1 (Section 3.1), Theorem 3 (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.

heading: 2 Our Techniques and Results

heading: 2.1 Preliminaries
text: Notations: Let round : R ! Z denote a function that returns the closest integer to a given real input. Let 1n denote a length n vector of all 1’s. We will write [n] to denote the set {1, . . . , n} and let P([n]) be the power set of [n]. For a vector v 2 Rn, let vi denote its i-th coordinate for any i 2 [n]. We will use supp(v) ✓ [n] 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
indicator vector of length n that takes 1 at index i if and only if vi 6= 0. For a vector v 2 Rn and subset S ✓ [n] of indices, let v|S 2 R|S| denote the vector v restricted to the indices in S. Finally, let f : P([n])⇥ {0, 1}n ! {0, 1}n be a function that takes a binary vector v 2 {0, 1}n and a subset S ✓ [n] as input and returns another binary vector v0 such that the indices of v corresponding to the the set S are flipped i.e. v0i = vi 1 if i 2 S and v0i = vi otherwise.
Tensor Decomposition: Consider a tensor A of order w 2 N, w > 2 on Rn which is denoted by A 2 Rn ⌦ Rn ⌦ · · · ⌦ Rn (w times). Let us denote by Ai1,i2,...,iw where i1, i2, . . . , iw 2 [n], the element in A whose location along the jth dimension is ij i.e. there are ij 1 elements along the jth dimension before Ai1,i2,...,iw . Notice that this indexing protocol uniquely determines the element within the tensor. For a detailed review of tensors, we defer the reader to [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 as
A = z⌦ z⌦ · · ·⌦ z| {z } w times
for some z 2 Rn i.e. Ai1,i2,...,iw = Qw
j=1 zij . A tensor A that can be expressed as a sum of R rank-1 symmetric tensors is defined as a rank R symmetric tensor. For such a rank R tensor A provided as input, we are concerned with the problem of unique decomposition of A into a sum of R rank-1 symmetric tensors; such a 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: Lemma 1 (Unique CP decomposition [40]). Suppose A is the sum of R rank-one tensors i.e.
A = RX
r=1 zr ⌦ zr ⌦ · · ·⌦ zr| {z } w times .
and further, the Kruskal Rank of the n⇥R matrix whose columns are formed by z1, z2, . . . , zR is J . Then, if wJ 2R+ (w 1), then the CP decomposition is unique and we can recover the vectors z1, z2, . . . , zR up to permutations.
There exist many different techniques for CP decomposition of a tensor but the most well-studied ones are Jennrich’s Algorithm (see Section 3.3, [32]) and the Alternating Least Squares (ALS) algorithm [28]. Among these, Jennrich’s algorithm (see Section E for more details) is efficient and recovers the latent rank-1 tensors uniquely but it works only for tensors of order 3 when the underlying vectors z1, z2, . . . , zR 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 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 tensors i.e.,
A = RX
r=1
r z r ⌦ zr ⌦ · · ·⌦ zr| {z }
w times
.
then we can rewrite A = PR
r=1 y r ⌦ yr ⌦ · · ·⌦ yr where yr = 1/wr zr. If {yr}Rr=1 satisfies the
conditions of Lemma 1 and if it is known that {zr}Rr=1 are binary vectors, then we can still recover zr by first computing yr and then taking its support for all r 2 [R]. Subsequently, notice that we can also recover { r}Rr=1. 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 > 3 could not be used. However, if it is known apriori that the vectors {zr}Rr=1 are binary and the coefficients { r}Rr=1 are positive integers bounded from above by some C > 0, then we can exhaustively search over all possibilities (O(C2n) 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 to be sparse as is true in our setting.

heading: 2.2 Our Techniques
text: Recall that the set of unknown vectors is denoted by V ⌘ {v1,v2, . . . ,v`}. Let A 2 {0, 1}n⇥` denote the support matrix corresponding to V where each column vector Ai 2 {0, 1}n represents the support of the ith unknown vector vi. For any ordered tuple C ⇢ [n] of indices, and any binary string a 2 {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 C, i.e.,
occ(C,a) := {vi 2 V | supp vi |C = a}.
In order to describe our techniques and our results, we need to introduce three different properties of matrices and extend them to a set 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 Ai of a binary matrix A 2 {0, 1}n⇥` with all distinct columns is called p-identifiable if there exists a set S ⇢ [n] of at most p-indices and a binary string a 2 {0, 1}p such that Ai|S = a, and Aj |S 6= a for all j 6= i.
A binary matrix A 2 {0, 1}n⇥` with all distinct columns is called p-identifiable if there exists a permutation : [`]! [`] such that for all i 2 [`], the sub-matrix Ai formed by deleting the columns indexed by the set { (1), (2), . . . , (i 1)} has at least one p-identifiable column.
Let V be set of ` unknown vectors in Rn, and A 2 {0, 1}n⇥` 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 1 uses the property that the support matrix A is p-identifiable for some known p  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 2 V , there exists a unique index i 2 [n] such that occ((i), 1) = {v}, and hence |occ((i), 1)| = 1. Observe that if |occ((i), 1)| = 1, and |occ((i, j), (1, 1))| = 1 for some i 6= j, then it follows that both the indices i, 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 2 [n]. The crux of their algorithm lies in computing all the n values of |occ((i), 1)|, and O(n2) values of |occ((i, j), (1, 1))| using just poly(`, 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 2 V that has a unique sub-string of length at most p. Hence, there exists a unique set C ✓ [n] and string a 2 {0, 1}|C| satisfying |C|  p such that occ(C [ {j}, (a, 1)) = {v}. By a similar observation as before, if |occ(C [ {j}, (a, 1))| = 1 for some j 2 [n] \ C, we can certify that j 2 supp(v) and if |occ(C [ {j}, (a, 1))| = 0, then j 62 supp(v). Hence we can reconstruct the support of v and subsequently, we can update |occ(C,a)| |occ(C,a)| 1[supp(v)|C = a] for all sets C satisfying |C|  p and all a 2 {0, 1}|C|. 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 p identifiable, 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 O(2pnp) values |occ(C,a)| for every p and, p + 1-sized ordered tuples of indices and all a 2 {0, 1}p [ {0, 1}p+1 (Lemma 2) using few queries. Definition 2 (flip-independent). A binary matrix A with all distinct columns is called flip-independent if there exists a subset of rows that if complemented (changing 0 to 1 and 1 to 0) make all columns of A linearly independent.
Let V be a set of ` unknown vectors in Rn, and A 2 {0, 1}n⇥` be its support matrix. Let B be the matrix obtained by deleting duplicate columns of A. The set V has flip-independent supports if B is flip-independent.
Support matrix is flip-independent: Algorithm 2 uses the property that the support matrix A is flip-independent in order to recover the supports of the unknown vectors uniquely. As a preprocessing step, we identify the set U , [i2[`]supp(vi) that represents the union of support of the unknown vectors. Let us define U 0 , 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 2 {0, 1}3, Algorithm 2 recovers |occ((i1, i2, i3),a)| for every ordered tuple (i1, i2, i3) 2 U3. Using these recovered quantities, it is possible to construct the tensors
AF = X
i2[`]
f(F , supp(vi))⌦ f(F , supp(vi))⌦ f(F , supp(vi))
for every subset F ✓ U 0. Since the matrix A is flip-independent, we know that there exists at least one subset F? ✓ U 0 such that the vectors {f(F?, supp(vi))}`i=1 are linearly independent. From Lemma 1, we know that by a CP decomposition of AF? , we can uniquely recover the vectors {f(F?, supp(vi))}`i=1; since the set F? is known, we can recover all the vectors {supp(vi))}`i=1 by flipping all indices corresponding to F?. However, a remaining challenge is to correctly identify a set F?. Interestingly, Jennrich’s algorithm (see Algorithm 8 in Appendix E) throws an error if the tensor AF under consideration does not satisfy the uniqueness conditions for CP decomposition i.e. the underlying unknown vectors {f(F , supp(vi))}`i=1 are not linearly independent. Therefore Algorithm 2 is guaranteed to uniquely recover the supports of the unknown vectors. 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 4 (r-Kruskal rank support). Let V be a set of ` unknown vectors in Rn, and A 2 {0, 1}n⇥` 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 , [i2[`]supp(vi) that represents the union of support of the unknown vectors. Note that |U|  `k since each unknown vector is k-sparse. Since Jennrich’s algorithm is not applicable for tensors of order more than 3, we will simply search over all O((`k)`k) possibilities in 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 to completely generalize Algorithm 2 by constructing multiple tensors of higher order. To circumvent this issue, Algorithm 3 constructs only a single tensor A of rank ` and order w = d 2` 1r 1 e by setting its (i1, . . . , iw)-th entry to |occ((i1, . . . , iw),1w)| for every ordered tuple (i1, . . . , iw) 2 [n]w. 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 s > 1 computes |occ(C,a)| for every s-sized ordered tuple of indices C, and any a 2 {0, 1}s 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.

heading: 2.3 Our Results
text: The MLC results below explicitly show the scaling with the noise, whereas all of the MLR query results below are valid with
SNR = O(`2 max i2[`] vi 2 2 / 2).
In our first result, we recover the support of the unknown vectors with small number of label queries provided the support matrix of V is p-identifiable. Theorem 1. Let V be a set of ` unknown vectors in Rn such that V is p-indentifiable. Then, Algorithm 1 recovers the support of all the unknown vectors in V with probability at least 1 O (1/n) using either (1) O ⇣ `3(`k)p+2 log(`kn) logn
(1 2⌘)2
⌘ MLC queries or (2) O(`3(`k)p+2 log(`kn) log n)
MLR queries.
In fact, all binary matrices with distinct columns are p-identifiable for some sufficiently large p. Theorem 2. Any n ⇥ `, (with n > `) binary matrix with all distinct columns is p-identifiable for some p  log `.
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 Rn. Then, Algorithm 1 recovers the support of all the unknown vectors in V with probability at least 1 O (1/n) using either (1) O ⇣
`3(`k)log `+2 log(`kn) logn (1 2⌘)2
⌘ MLC queries or (2) O(`3(`k)log `+2 log(`kn) log n) MLR queries.
Proof. The proof follows from the fact that any set V of ` unknown vectors in Rn must have p-identifiable supports for p  log `.
Under some assumptions on the unknown support, e.g.flip-independence, we have better results. Theorem 3. Let V be a set of ` unknown vectors in Rn such that V is flip-independent. Then, Algorithm 2 recovers the support of all the unknown vectors in V with probability at least 1 O (1/n) using either (1) O ⇣ `3(`k)4 log(`kn) logn
(1 2⌘)2
⌘ MLC queries or (2) O(`3(`k)4 log(`kn) log n)
MLR queries.
We can also leverage the property of small Kruskal rank of the support matrix to show: Theorem 4. Let V be a set of ` unknown vectors in Rn that has r-Kruskal rank support with r 2. Let w = d 2` 1r 1 e. Then, Algorithm 3 recovers the support of all the unknown vectors in V with probability at least 1 O (1/n) using either (1) O ⇣ `3(`k)w+1 log(`kn) logn
(1 2⌘)2
⌘ MLC queries or (2)
O(`3(`k)w+1 log(`kn) log n) MLR queries.
Discussion on 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 assumptions (Corollary 1). The flip-independence (Definition 2) and r-Kruskal rank support (Definition 4) properties are used for the tensor-decomposition 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
M =
2
64 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1
3
75
is not flip independent. The r-Kruskal rank support condition generalizes linear independence conditions considered in previous mixture model studies such as [45]. Note that this condition is always satisfied by the support vectors for some r 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-time of our algorithms in this work, we report the relevant computational complexities below: Remark 5 (Computational Complexity). Note that Algorithm 1 has a computational complexity that is polynomial in the sparsity k, dimension n and scales as O(`p) where p  log `. On the other hand Algorithms 2, 3 has a computational complexity that scales exponentially with k, ` while remaining polynomial in the dimension n. For the special case when the support matrix is known to be full rank, Algorithm 3 with w = 3 is polynomial in all parameters (by using Algorithm 8 for the CP decomposition.)

heading: 3 Detailed Proofs and Algorithms
text: Recall the definition of occ(C,a) - the number of unknown vectors whose supports have a 2 {0, 1}|C| as a substring in coordinates C ⇢ [n]. First, we observe that for any set T ✓ {0, 1}s, we can compute |occ(C,a)| for all O(ns) subsets of s indices C ⇢ [n] and a 2 T using few MLC or MLR queries.
Lemma 2. Let T ✓ {0, 1}s be any set of binary vectors of length s. There exists an algorithm to compute |occ(C,a)| for all C ⇢ [n] of size s, and all a 2 T with probability at least 1 1/n using either O(`3(`k)s+1 log(`kn) log n/(1 2⌘)2) MLC queries or O(`3(`k)s+1 log(`kn) log n) MLR queries.
Lemma 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 ⌘ {v1, . . . ,v`} when V is p-identifiable. In particular, we show that if V is p-identifiable, then computing |occ(C,a)| for every subset of p and p+ 1 indices is sufficient to recover the supports.
Proof of Theorem 1. The proof follows from the observation that for any subset of p indices C ⇢ [n], index j 2 [n] \ C and a 2 {0, 1}p, |occ(C,a)| = |occ(C [ {j}, (a, 1))| + |occ(C [ {j}, (a, 0))|. Therefore if one of the terms in the RHS is 0 for all j 2 [n] \ C, then all the vectors in occ(C,a) share the same support.
Also, if some two vectors u,v 2 occ(C,a) do not have the same support, then there will exist at least one index j 2 [n] \C such that u 2 occ(C [ {j}, (a, 1))| and v 2 occ(C [ {j}, (a, 0)) or the other way round, and therefore |occ(C [ {j}, (a, 1))| 62 {0, |occ(C,a)|}. Algorithm 1 precisely checks for this condition. The existence of some vector v 2 V (p-identifiable column), a subset of indices C ⇢ [n] of size p, and a binary sub-string b 2 {0, 1}p follows from the fact that V is p-identifiable. Let us denote the subset of unknown vectors with distinct support in V by V1. Once we recover the p-identifiable column of V1, we mark it as u1 and remove it from the set (if there are multiple p-identifiable columns, we arbitrarily choose one of them). Subsequently, we can modify the |occ(·)| values for all S ✓ [n], |S| 2 {p, p+ 1} and t 2 {0, 1}p [ {0, 1}p+1 as follows:
occ2(S, t) , |occ(S, t)| |occ(C,b)|⇥ 1[supp u1 |S = t]. (2)
Notice that, Equation 2 computes occ2(S, t) = {vi 2 V2 | supp vi |S = t} where V2 is formed by deleting all copies of u1 from V . Since V1 is p-identifiable, there exists a p-identifiable column in V1 \ {u1} as well which we can recover. More generally for q > 2, if uq 1 is the p-identifiable column with the unique binary sub-string bq 1 corresponding to the set of indices Cq 1, we will have for all S ✓ [n], |S| 2 {p, p+ 1} and t 2 {0, 1}p [ {0, 1}p+1
|occq(S, t)| , occq 1(S, t)
occq 1(Cq 1,bq 1) ⇥ 1[supp uq 1 |S = t]
implying |occq(S, t)| = {vi 2 Vq | supp vi |S = t} where Vq is formed deleting all copies of u1,u2, . . . ,uq 1 from V . Applying these steps recursively and repeatedly using the property that V is p-identifiable, we can recover all the support of all the vectors present in V .
Algorithm 1 requires the values of |occ(C,a)|, and |occ(C̃, ã)| for every p and p+ 1 sized subset of indices C, C̃ ⇢ [n], and every a 2 {0, 1}p, ã 2 {0, 1}p+1. Using Lemma 2, we can compute all these values using O(`3(`k)p+2 log(`kn) log n/(1 2⌘)2) MLC queries or O(`3(`k)p+2 log(`kn) log n) MLR queries with probability at least 1 O(n 1).

heading: 3.2 Recovery of flip-independent support matrix
text: In this section, we 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 1 O(1/n), we can compute |occ(C, ·)| using O(`3(`k)4 log(`kn) log n/(1 2⌘)2) MLC queries or O(`3(`k)4 log(`kn) log n) MLR queries. For every subset F ✓ U 0, we construct the tensor AF as follows: AF(i1,i2,i3) = |occ((i1, i2, i3), (ai1, ai2, ai3))|, for all (i1, i2, i3) 2 [n]3 where aij = 0 if ij 2 F and 1 otherwise. We then run Jenerich’s algorithm on each AF . Observe that for any binary vector b 2 {0, 1}n,
Algorithm 1 RECOVER p-IDENTIFIABLE SUPPORTS
Require: |occ(C,a)| for every C ⇢ [n], |C| = t, t 2 {p, p+1}, and every a 2 {0, 1}p[{0, 1}p+1. 1: Set count = 1, i = 1. 2: while count  ` do 3: if |occ(C,a)| = w, and |occ(C [ {j}, (a, 1))| 2 {0, w} for all j 2 [n] \ C then 4: Set supp ui |C = a
5: For every j 2 [n] \ C, set supp ui |j = b, where |occ(C [ {j}, (a, b))| = w. 6: Set Multiplicityi = w. 7: For all t 2 {0, 1}p [ {0, 1}p+1, S ✓ [n] such that |S| 2 {p, p+ 1}, update
|occ(S, t)| |occ(S, t)| |occ(C,a)|⇥ 1[supp ui |S = t]
8: count = count + w. 9: i = i+ 1.
10: end if 11: end while 12: Return Multiplicityj copies of supp uj for all j < i.
Algorithm 2 RECOVER FLIP-INDEPENDENT SUPPORTS
Require: |occ(C,a)| for every C ⇢ [n], such that |C| = 3, and all a 2 {0, 1}3. |occ(i, 1)| for all i 2 [n].
1: Set U = {i 2 [n] : |occ(i, 1)| 6= 0} and U 0 = U [ {t} where t 2 [n] \ U . 2: for each F ⇢ U 0 do 3: Construct tensor AF as follows: 4: for every (i1, i2, i3) 2 [n]3 do 5: Set AF(i1,i2,i3) = |occ((i1, i2, i3), (ai1, ai2, ai3))|, where aij = 0 if ij 2 F and 1 otherwise. 6: end for 7: if Jenerich(AF ) (Algorithm 8 with input AF ) succeeds: then 8: Let AF = PR i=1 ia
i ⌦ ai ⌦ ai be the tensor decomposition of A such that ai 2 {0, 1}n. 9: For all i 2 [R], modify ai by flipping entries in F .
10: Return i columns with modified ai, 8i 2 [R]. 11: break 12: end if 13: end for
the (i1, i2, i3)-th entry of the rank-1 tensor b⌦ b⌦ b is 1 if bi1 = bi2 = bi3 = 1, and 0 otherwise. Therefore, the tensor AF can be decomposed as AF = PR i=1 ia
i ⌦ ai ⌦ ai, where the vectors ai 2 {0, 1}n, i 2 R are the support vectors (of the R distinct unknown vectors) that are flipped at indices in F with multiplicity i. Now if the support matrix of the unknown vectors is flip-independent, then there exists a subset of rows indexed by some F? ✓ [n] (and furthermore, F? ✓ U 0) such that flipping the entries of those rows results in a 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 or not), we can search for F? as a subset of U 0. Since, |U 0|  `k + 1, this step improves the search space for F? from O(2n) to O(2`k).
Therefore, Jennrich’s algorithm on input AF? is guaranteed to succeed and returns the decomposition AF? = PR i=1 ia
i ⌦ ai ⌦ ai as the sum of R rank-one tensors, where, ai 2 {0, 1}n, i 2 [R] are modified support vectors (with multiplicity i). Subsequently, we can again flip the entries of the recovered vectors indexed by F? to return the original support vectors.
Algorithm 3 RECOVER r-KRUSKAL RANK SUPPORTS
1: Let w be smallest integer such that w · (r 1) 2` 1. Require: |occ(C,1w)| for every C ⇢ [n] with |C| = w. |occ(i, 1)| for all i 2 [n].
2: Set U , {i 2 [n] : |occ(i, 1)| 6= 0}. 3: Construct tensor A as follows: 4: for every (i1, . . . , iw) 2 [n]w do 5: Set A(i1,...,iw) = |occ((i1, . . . , iw),1w)|. 6: end for 7: for every (b1,b2 . . . ,b`) 2 {0, 1}n satisfying supp(bi) ✓ U do 8: if A = P` i=1 b
i ⌦ bi · · ·⌦ bi (w times) then 9: Set (b1,b2 . . . ,b`) to be the CP decomposition of A and Break
10: end if 11: end for 12: Return CP decomposition of A
3.3 Recovery of r-Kruskal rank supports
In this section, we present an algorithm that recovers the support of all the ` unknown vectors provided they have r-Kruskal rank supports. Recall that for any set of w indices C ⇢ [n], occ(C,1w) denotes the set of unknown vectors that are supported on all indices in C.
Proof of Theorem 4. To recover the supports we first construct the following order w tensor: A(i1,...,iw) = |occ((i1, . . . , iw),1w)|, for (i1, . . . , iw) 2 [n]w. Observe that the tensor A can be written as the sum of `0 (`0 < `) rank one tensors
A = `0X
i=1
i supp vi ⌦ . . .⌦ supp vi
| {z } w-times
. (3)
where v1,v2, . . . ,v` 0
are the unknown vectors with distinct supports in V with i being the multiplicity of supp vi . Since the support matrix A of V has r-Kruskal rank, for any w such that w · (r 1) 2` 1, the decomposition of Eq. (3) is unique (Lemma 1). Notice that by a preprocessing step, we compute U , {i 2 [n] : |occ(i, 1)| 6= 0} to 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((`k)`k) of them (Steps 7-10) to find the unique CP decomposition of the tensor A. For the special case when w = 3, Jennrich’s algorithm (Algorithm 8) can be used to efficiently compute the unique CP decomposition of the tensor A. Algorithm 3 needs to know the values of |occ(C,1w)| for every C ⇢ [n], such that |C| = w. Using Lemma 2, these can be computed using O(`3(`k)w+1 log(`kn) log n/(1 2⌘)2) MLC queries or O(`3(`k)w+1 log(`kn) log n) MLR queries with probability at least 1 O(1/n).
Acknowledgements: This work is supported in part by NSF awards 2133484, 2127929, and 1934846.

Review summaries:
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).   In 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.   The 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. 

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.

 The paper addresses a generalized problem in 1-bit compressed sensing, considered in several papers [9, 19, 27, 29]. The problem is to recovery the supports of ALL of l unknown k-sparse vectors from 1-bit noisy measurements based on a sufficient number of query vectors (See Sec. 1.1). The problem is addressed for both mixture of linear classifiers (MLC) and mixture of linear regressions (MLR).   Corollary 1 provides sufficient conditions for the number of queries to recover the supports with asymptotically probability 1. The corollary follows immediately from Theorems 1 and 2 based on the notion of an identifiable set of l sparse vectors in Definition 1. Theorem 3 postulates a flip-independent set of l sparse vectors in Definition 2 to use Jenerich’s algorithm for the canonical polyadic (CP) decomposition of a tensor. Theorem 4 postulates that the set of sparse vectors has a known Kruskal rank r to guarantee the uniqueness of the CP decomposition. Theorem 3 provides a tighter sufficient condition than Corollary 1 for l>4 while Theorem 4 is tighter than Theorem 2 for (2l-1)<(r-1)(log l + 2), which holds for small l.   

The authors consider the problem of recovering the support of multiple sparse vectors from a noisy mixture of linear measurements (i.e., mixed linear regression), and from a noisy mixture of signed measurements (i.e., mixed linear classification). That is, each measurement corresponds to one of the unknown sparse vectors, but which vector is unknown.  For these problems, they propose three algorithms, each of which can be applied to either mixed regression or mixed classification. Furthermore, they provide guarantees on the number of measurements that needs to be collected to recover the support with high probability.  The guarantees for their first algorithm hold when the support matrix is p-identifiable, but worst-case guarantees that do not require p-identifiability are also given. Stronger guarantees hold for their second algorithm in the case that the unknown supports are flip-independent. Finally, guarantees hold for the third algorithm when the support matrix has small Kruksal rank.