Reed Muller Sensing Matrices and the LASSO

Details Reed Muller Sensing Matrices and the LASSO Reed Muller Sensing Matrices and the LASSO

2010-04-28

arxiv.org/abs/1004.4949v1

Computer Science

Information Theory

Scientific paper

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 $2^m$ - dimensional tight frames with redundancy $2^{rm}$. 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\leq 15$ and $r\geq2$ 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.

Affiliated with

Also associated with

No associations

Rating

Reed Muller Sensing Matrices and the LASSO does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reed Muller Sensing Matrices and the LASSO, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed Muller Sensing Matrices and the LASSO will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67639