Skip to main content

Reed Muller sensing matrices and the LASSO (Invited paper)

Publication ,  Journal Article
Calderbank, R; Jafarpour, S
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
November 19, 2010

We construct two families of deterministic sensing matrices where the columns are obtained by exponentiating codewords in the quaternary Delsarte-Goethals code DG(m,r). This method of construction results in sensing matrices with low coherence and spectral norm. The first family, which we call Delsarte-Goethals frames, are 2m - dimensional tight frames with redundancy 2rm . The second family, which we call Delsarte-Goethals sieves, are obtained by subsampling the column vectors in a Delsarte-Goethals frame. Different rows of a Delsarte-Goethals sieve may not be orthogonal, and we present an effective algorithm for identifying all pairs of non-orthogonal rows. The pairs turn out to be duplicate measurements and eliminating them leads to a tight frame. Experimental results suggest that all DG(m,r) sieves with m ≤ 15 and r ≥ 2 are tight-frames; there are no duplicate rows. For both families of sensing matrices, we measure accuracy of reconstruction (statistical 0 - 1 loss) and complexity (average reconstruction time) as a function of the sparsity level k. Our results show that DG frames and sieves outperform random Gaussian matrices in terms of noiseless and noisy signal recovery using the LASSO. © 2010 Springer-Verlag.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

November 19, 2010

Volume

6338 LNCS

Start / End Page

442 / 463

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, R., & Jafarpour, S. (2010). Reed Muller sensing matrices and the LASSO (Invited paper). Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6338 LNCS, 442–463. https://doi.org/10.1007/978-3-642-15874-2_37
Calderbank, R., and S. Jafarpour. “Reed Muller sensing matrices and the LASSO (Invited paper).” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6338 LNCS (November 19, 2010): 442–63. https://doi.org/10.1007/978-3-642-15874-2_37.
Calderbank R, Jafarpour S. Reed Muller sensing matrices and the LASSO (Invited paper). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010 Nov 19;6338 LNCS:442–63.
Calderbank, R., and S. Jafarpour. “Reed Muller sensing matrices and the LASSO (Invited paper).” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6338 LNCS, Nov. 2010, pp. 442–63. Scopus, doi:10.1007/978-3-642-15874-2_37.
Calderbank R, Jafarpour S. Reed Muller sensing matrices and the LASSO (Invited paper). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010 Nov 19;6338 LNCS:442–463.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

November 19, 2010

Volume

6338 LNCS

Start / End Page

442 / 463

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences