This paper introduces the Witness-Averaging Algorithm for sparse reconstruction using the Reed Muller sieve. The Reed-Muller sieve is a deterministic measurement matrix for compressed sensing. The columns of this matrix are obtained by exponentiating codewords in the quaternary second order Reed Muller code of length $N$. For $k=tilde{O}left(mm right)$, the Witness-Averaging improves upon prior methods for identifying the textit{support} of a $k$-sparse vector by removing the requirement that the signal entries be independent, and by providing computational efficiency. It also enables local detection; that is, the proposed algorithm detects the presence or absence of a signal at any given position in the data domain without explicitly reconstructing the entire signal. Reconstruction is shown to be resilient to noise in both the measurement and data domains; the textit{average-case} $ell_2 / ell_2$ error bounds derived in this paper are tighter than the textit{worst-case} $ell_2 / ell_1$ bounds arising from random ensembles.