Sparse Approximation and Compressed Sensing Using the Reed-Muller Sieve

Abstract:

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.