Math @ Duke

Publications [#235964] of Robert Calderbank
Papers Published
 Calderbank, R; Jafarpour, S, Reed Muller sensing matrices and the LASSO (Invited paper),
Lecture notes in computer science, vol. 6338 LNCS
(2010),
pp. 442463, ISSN 03029743 [doi]
(last updated on 2018/07/18)
Abstract: We construct two families of deterministic sensing matrices where the columns are obtained by exponentiating codewords in the quaternary DelsarteGoethals code DG(m,r). This method of construction results in sensing matrices with low coherence and spectral norm. The first family, which we call DelsarteGoethals frames, are 2m  dimensional tight frames with redundancy 2rm . The second family, which we call DelsarteGoethals sieves, are obtained by subsampling the column vectors in a DelsarteGoethals frame. Different rows of a DelsarteGoethals sieve may not be orthogonal, and we present an effective algorithm for identifying all pairs of nonorthogonal 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 tightframes; 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 SpringerVerlag.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

