A fast reconstruction algorithm for deterministic compressive sensing using second order reed-muller codes


Journal Article

This paper proposes a deterministic compressed sensing matrix that comes by design with a very fast reconstruction algorithm, in the sense that its complexity depends only on the number of measurements n and not on the signal dimension N. The matrix construction is based on the second order Reed-Muller codes and associated functions. This matrix does not have RIP uniformly with respect to all k-sparse vectors, but it acts as a near isometry on k-sparse vectors with very high probability. © 2008 IEEE.

Full Text

Duke Authors

Cited Authors

  • Howard, SD; Calderbank, AR; Searle, SJ

Published Date

  • September 22, 2008

Published In

  • Ciss 2008, the 42nd Annual Conference on Information Sciences and Systems

Start / End Page

  • 11 - 15

Digital Object Identifier (DOI)

  • 10.1109/CISS.2008.4558486

Citation Source

  • Scopus