University of Cambridge > > Signal Processing and Communications Lab Seminars > Toward Sparse and Structured Projections for Compressed Sensing

Toward Sparse and Structured Projections for Compressed Sensing

Add to your list(s) Download to your calendar using vCal

  • UserProf Hayder Radha, Department of Electrical and Computer Engineering Michigan State University
  • ClockThursday 30 July 2009, 14:15-15:15
  • HouseLR5, Engineering, Department of.

If you have a question about this talk, please contact Rachel Fogg.

The problem of finding the unique (sparsest) solution (/x/) to an underdetermined system: /y/ = /Px/, is at the core of many problems in signal processing, including compressed sensing. The required methods for solving this profound problem are significantly influenced by the choice of the projection/measurement matrix /P/. Consequently, the notion of categorizing projection matrices, with common attributes, into an ensemble /A/ have been employed in an effort to develop better understanding of the influence of projection matrices on the aforementioned problem. Popular matrix ensembles, which are quite simple to construct and which have been studied thoroughly, include the Gaussian ensemble and partial Fourier ensemble. In this seminar, two new directions in the design of projection ensembles for compressed sensing will be outlined. First, we show that new designs that are sparse in nature provide significant reductions in computational complexity. It can be shown that certain class of random sparse projections, when operating on a /k/-sparse signal of length /n/, requires /m/ = O(/Ck/)/ /compressive samples for perfect recovery, where /C/ is independent of /n/. More importantly, the decoder complexity is lower than the complexity of greedy algorithms. Second, we present another class of projections where the ensembles are designed with some underlying structure imposed on random sparse matrices. These matrices are known as Complex Randomness-in-Structured Projection (CRISP) ensembles. CRISP matrices recover a sparse signal with significantly less compressive samples at the expense of a slight increase in solver complexity relative to unstructured random sparse projections. Our simulation results demonstrate the CRISP framework’s ability to recover a signal in situations where the rather-complex Basis Pursuit approach fails to do so, and meanwhile, the required time for recovery is less than the time required by Orthogonal Matching Pursuit, a well known greedy algorithm. These new design examples highlight the importance of pursuing sparse and structured projection ensembles for compressed sensing.

This talk is part of the Signal Processing and Communications Lab Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2017, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity