Deterministic constructions of compressed sensing matrices Academic Article uri icon


  • Compressed sensing is a new area of signal processing. Its goal is to minimize the number of samples that need to be taken from a signal for faithful reconstruction. The performance of compressed sensing on signal classes is directly related to Gelfand widths. Similar to the deeper constructions of optimal subspaces in Gelfand widths, most sampling algorithms are based on randomization. However, for possible circuit implementation, it is important to understand what can be done with purely deterministic sampling. In this note, we show how to construct sampling matrices using finite fields. One such construction gives cyclic matrices which are interesting for circuit implementation. While the guaranteed performance of these deterministic constructions is not comparable to the random constructions, these matrices have the best known performance for purely deterministic constructions. 2007 Elsevier Inc. All rights reserved.

published proceedings

  • Journal of Complexity

altmetric score

  • 6

author list (cited authors)

  • DeVore, R. A.

citation count

  • 395

complete list of authors

  • DeVore, Ronald A

publication date

  • January 2007