Randomly aggregated least squares for support recovery

We study the problem of exact support recovery: given an (unknown) vector with known sparsity we are given access to the noisy measurementwhere is a (known) Gaussian matrix and the noise is an (unknown) Gaussian vector. How small can be for reliable recovery of the support of ? We present RAWLS (andomly ggregated uneighted east Squares upport Recovery): the main idea is to take random subsets of the equations, perform least squares over this reduced bit of information, and average over many random subsets. We show that the proposed procedure can provably recover an approximation of and demonstrate its use through numerical examples. We use numerical simulations to demonstrate that the proposed procedure is beneficial for the task of support recovery. Finally, we observe that RAWLS is at par with several strong baselines in the low information regime (i.e. is small or is large).