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.


Reviews:
[{"review_id": "tk8FshFjimc", "reviewer": "Reviewer_kx4J", "summary": "This paper studies the problem of recovering the supports of multiple sparse signals from a mixture of measurements, in both \"mixture of linear regressions\" and \"mixture of linear classifiers\" settings. It proposes three algorithms, each with theoretical guarantees under different technical assumptions.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "This work makes good theoretical contributions to understanding and solving the problem of support recovery in the mixture models. It identifies three key assumptions (which are milder than those in the existing literature) that enables support recovery with near-polynomial query complexity, though some of the algorithms are computationally inefficient. The comparison with prior work is rather complete. The overall writing is quite polished, and the paper's structure is clean. The technical parts are quite involved and out of my expertise, so I cannot comment much on it.\n\nI hope the authors can address the following concerns:\n* Line 16 claims \"a number of measurements ... quasi-polynomial in $l$\". However, the query complexity in Theorem 4 involves $(lk)^{w+1}$, where $w \\propto l$. Doesn't this imply an exponential dependence on $l$?\n* Line 165: when defining \"occ\", explaining what these letters stand for might be helpful for understanding.\n* Line 283 claims \"without any assumptions\"; it might be fairer to say \"with mild assumptions\", since the three conditions on support matrix ($p$-identifiable, flip-independent, Kruskal rank) are indeed assumptions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "hkAQPBoCQwO", "reviewer": "Reviewer_a6qx", "summary": " 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). \n\nCorollary 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.  \n", "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": "Originality\n\n The main originality is in Lemma 2, claiming the existence of an algorithm to count the size of the set occ(C, a) of unknown vectors of which corresponding supports have a substring a at positions indexed by C for all C and a (See Sec. 2.2). In fact, Theorem 1 is based on Algorithm 1, which utilizes the identifiability and the size |occ(,)|. Theorems 3 and 4 also use the size |occ(,)|. As a result, these theorems claim similar orders in l, k, and n, which originate from Lemma 2. \n The proof of Lemma 2 in the supplementary material is based on two subroutines to count the sizes |\\cup_i occ((i),1)| and |occ((i),1)|. The former is counted via Algorithm 4 using a cover free family (CFF) [24] of queries in Definition 7 while the latter is computed via Algorithm 5 using a robust union free family (RUFF) [16] of queries in Definition 6. Lemma 2 is proven by combining the two algorithms. \n\nQuality\n\nThe tightness of Corollary 1 and Theorems 3, 4 (or essentially Lemma 2) is not discussed. Compare them with state-of-the-art results and clarify whether the bounds are tight. \n\nClarity\n\n The paper is well organized. The main idea of the proof strategy is outlined in Sec. 2.2. While Lemma 2 is the main result, the proof of Lemma 2 is technically complicated. Thus, the proof is presented in the supplementary material. The proofs of Theorems 1, 3, and 4 are easy to follow since the proof strategy has been clarified in Sec. 2.2. Nonetheless, I have several comments for a further improvement.\n\n--In Sec. 2.1, the authors regard that the unique CP decomposition indicates trivially correct support recovery and therefore present no explanation. An addition of a brief explanation for this point should improve the readability in understanding Theorems 3 and 4.  \n\n--it would be better to clarify the meaning of “occ” in Sec. 2.2. In the definition of occ(C, a), clarify that supp(v^i) represents the binary indicator vector of length n. \n\n--The authors should be mathematically careful in the descriptions after “if A is p-identifiable, then the set of distinct support vectors have a unique sub-string of length at most p,” in terms of some or all. In my understanding, “for each unknown vector” in line 195 should be “for some unknown vector.” Is “unique” correct in line 196. I do not understand why the uniqueness is required. The first j in line 197 should be all j/in C\\backslash supp(v). Thus, “for some j” in line 198 is not appropriate.  \n\nSignificance \n\n In the proof of Lemma 2, the construction of CFF is information-theoretic (not constructive). As a result, the authors cannot simulate the algorithms used in the proofs. I believe that NeurIPS requires not only theoretical results but also practical algorithms unless the theoretical results are extremely novel results. \n\n--It would be better to present a practical construction of CFFs even if the construction is suboptimal.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " As pointed out in Significance, the paper is information-theoretic and cannot simulate the algorithms numerically. As a result, the paper provides no negative social impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "_efw_SeOpIy", "reviewer": "Reviewer_MfJp", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "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 theoretical contributions seem to be very strong, although I must admit that this work is outside my area of expertise.\n\nOne small question concerns Theorem 2 and Corollary 1.  In Theorem 2, it says that all binary matrices with distinct columns are p-identifiable for p <= log ell.  But Corollary 1 seems to drop the requirement for the support matrix to have distinct columns, as does the phrase \"unconditional\" given before Corollary 1.  A similar confusion is caused by the sentences around line 372, which state, \"we will assume that all of the unknown vectors have distinct supports...However, this assumption is not necessary and all our algorithms work even when the supports are not distinct.\"  In summary, it is not quite clear which results require distinct supports and which do not.\n\nAlthough I understand that the primary contribution is theoretical, it would have been nice to see whether the proposed algorithms yield better empirical results than those of the prior work [44,27,29].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential for negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers have very positively received this paper; all marks match to a clear accept, that I will follow. The concerns by the reviewers seem to have been fully answered. Some reviewers pointed out the lack of numerical experiments, then provided by the authors answers. I believe that, as promised to some reviewers, the authors should definitely add these experiments, possibly in an appendix. Additionally, it seems that some definitions could be slightly more furnished to improve readability. I'm confident that the authors will implement these few improvements for the final version as suggested by the reviewers. Given the overall quality of redaction of the paper and the originality of the results, I recommend acceptance for a poster.
Decision: Accept (Poster)