mixture-main

The proof of the lemma follows from a simple application of Chernoff bound. Consider a matrix G of size m n where each entry is generated independently from a Bernoulli( p) distribution with p as a parameter. In this section, we prove the helper Lemmas 10 and 11 to compete the proof of Theorem 1 and also present the proof of Theorem 2. The two stage approximate recovery algorithm, as the name suggests, proceeds in two sequential steps. In the first stage, we recover the support of all the ` unknown vectors (presented in Algorithm 2 in Section 5). In the second stage, we use these deduced supports to approximately recover the unknown vectors (Algorithm 5 described in Section B.2). B.1 Support recovery (Missing proofs from Section 5) Compute |S ( i) | using Algorithm 3. First, we show how to compute |S ( i) | for every index i 2 [ n ] .