A robust parallel algorithm for combinatorial compressed sensing

Rodrigo Mendoza-Smith, Jared Tanner, Florian Wechsung

In previous work two of the authors have shown that a vector $x\in {\mathbb{R}}^n$ with at most $k<n$ nonzeros can be recovered from an expander sketch $Ax$ in $\mathcal{O}(\mathr…