  We introduce two new algorithms, Serial-$\ell_0$ and Parallel-$\ell_0$ for
solving a large underdetermined linear system of equations $y = Ax \in
\mathbb{R}^m$ when it is known that $x \in \mathbb{R}^n$ has at most $k < m$
nonzero entries and that $A$ is the adjacency matrix of an unbalanced left
$d$-regular expander graph. The matrices in this class are sparse and allow a
highly efficient implementation. A number of algorithms have been designed to
work exclusively under this setting, composing the branch of combinatorial
compressed-sensing (CCS).
  Serial-$\ell_0$ and Parallel-$\ell_0$ iteratively minimise $\|y - A\hat
x\|_0$ by successfully combining two desirable features of previous CCS
algorithms: the information-preserving strategy of ER, and the parallel
updating mechanism of SMP. We are able to link these elements and guarantee
convergence in $\mathcal{O}(dn \log k)$ operations by assuming that the signal
is dissociated, meaning that all of the $2^k$ subset sums of the support of $x$
are pairwise different. However, we observe empirically that the signal need
not be exactly dissociated in practice. Moreover, we observe Serial-$\ell_0$
and Parallel-$\ell_0$ to be able to solve large scale problems with a larger
fraction of nonzeros than other algorithms when the number of measurements is
substantially less than the signal length; in particular, they are able to
reliably solve for a $k$-sparse vector $x\in\mathbb{R}^n$ from $m$ expander
measurements with $n/m=10^3$ and $k/m$ up to four times greater than what is
achievable by $\ell_1$-regularization from dense Gaussian measurements.
Additionally, Serial-$\ell_0$ and Parallel-$\ell_0$ are observed to be able to
solve large problems sizes in substantially less time than other algorithms for
compressed sensing. In particular, Parallel-$\ell_0$ is structured to take
advantage of massively parallel architectures.
