# Sparse Reconstruction via The Reed-Muller Sieve - Computer Science > Information Theory

Abstract: This paper introduces the Reed Muller Sieve, a deterministic measurementmatrix for compressed sensing. The columns of this matrix are obtained byexponentiating codewords in the quaternary second order Reed Muller code oflength $N$. For $k=ON$, the Reed Muller Sieve improves upon prior methods foridentifying the support of a $k$-sparse vector by removing the requirement thatthe signal entries be independent. The Sieve also enables local detection; analgorithm is presented with complexity $N^2 \log N$ that detects the presenceor absence of a signal at any given position in the data domain withoutexplicitly reconstructing the entire signal. Reconstruction is shown to beresilient to noise in both the measurement and data domains; the $\ell 2 -\ell 2$ error bounds derived in this paper are tighter than the $\ell 2 -\ell 1$ bounds arising from random ensembles and the $\ell 1 -\ell 1$ boundsarising from expander-based ensembles.

Author: Robert Calderbank, Stephen Howard, Sina Jafarpour

Source: https://arxiv.org/