Skip to main content

Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property

Publication ,  Journal Article
Calderbank, R; Howard, S; Jafarpour, S
Published in: IEEE Journal on Selected Topics in Signal Processing
April 1, 2010

Compressed Sensing aims to capture attributes of κ-sparse signals using very few measurements. In the standard compressed sensing paradigm, the N × C measurement matrix Φ is required to act as a near isometry on the set of all κ-sparse signals (restricted isometry property or RIP). Although it is known that certain probabilistic processes generate N × C matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix Φ has this property, crucial for the feasibility of the standard recovery algorithms. In contrast, this paper provides simple criteria that guarantee that a deterministic sensing matrix satisfying these criteria acts as a near isometry on an overwhelming majority of κ-sparse signals; in particular, most such signals have a unique representation in the measurement domain. Probability still plays a critical role, but it enters the signal model rather than the construction of the sensing matrix. An essential element in our construction is that we require the columns of the sensing matrix to form a group under pointwise multiplication. The construction allows recovery methods for which the expected performance is sub-linear in C, and only quadratic in N, as compared to the super-linear complexity in C of the Basis Pursuit or Matching Pursuit algorithms; the focus on expected performance is more typical of mainstream signal processing than the worst case analysis that prevails in standard compressed sensing. Our framework encompasses many families of deterministic sensing matrices, including those formed from discrete chirps, DelsarteGoethals codes, and extended BCH codes. © IEEE.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Journal on Selected Topics in Signal Processing

DOI

ISSN

1932-4553

Publication Date

April 1, 2010

Volume

4

Issue

2

Start / End Page

358 / 374

Related Subject Headings

  • Networking & Telecommunications
  • 4603 Computer vision and multimedia computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, R., Howard, S., & Jafarpour, S. (2010). Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE Journal on Selected Topics in Signal Processing, 4(2), 358–374. https://doi.org/10.1109/JSTSP.2010.2043161
Calderbank, R., S. Howard, and S. Jafarpour. “Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property.” IEEE Journal on Selected Topics in Signal Processing 4, no. 2 (April 1, 2010): 358–74. https://doi.org/10.1109/JSTSP.2010.2043161.
Calderbank R, Howard S, Jafarpour S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE Journal on Selected Topics in Signal Processing. 2010 Apr 1;4(2):358–74.
Calderbank, R., et al. “Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property.” IEEE Journal on Selected Topics in Signal Processing, vol. 4, no. 2, Apr. 2010, pp. 358–74. Scopus, doi:10.1109/JSTSP.2010.2043161.
Calderbank R, Howard S, Jafarpour S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE Journal on Selected Topics in Signal Processing. 2010 Apr 1;4(2):358–374.

Published In

IEEE Journal on Selected Topics in Signal Processing

DOI

ISSN

1932-4553

Publication Date

April 1, 2010

Volume

4

Issue

2

Start / End Page

358 / 374

Related Subject Headings

  • Networking & Telecommunications
  • 4603 Computer vision and multimedia computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing