  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}(\mathrm{nnz}(A)\log k)$ operations via the
Parallel-$\ell_0$ decoding algorithm, where $\mathrm{nnz}(A)$ denotes the
number of nonzero entries in $A \in \mathbb{R}^{m \times n}$. In this paper we
present the Robust-$\ell_0$ decoding algorithm, which robustifies
Parallel-$\ell_0$ when the sketch $Ax$ is corrupted by additive noise. This
robustness is achieved by approximating the asymptotic posterior distribution
of values in the sketch given its corrupted measurements. We provide analytic
expressions that approximate these posteriors under the assumptions that the
nonzero entries in the signal and the noise are drawn from continuous
distributions. Numerical experiments presented show that Robust-$\ell_0$ is
superior to existing greedy and combinatorial compressed sensing algorithms in
the presence of small to moderate signal-to-noise ratios in the setting of
Gaussian signals and Gaussian additive noise.
