Toward Sparse and Structured Projections for Compressed Sensing

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

• Prof Hayder Radha, Department of Electrical and Computer Engineering Michigan State University
• Thursday 30 July 2009, 14:15-15:15
• LR5, 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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Featured lists
• Information Engineering Division seminar list
• Interested Talks
• LR5, Engineering, Department of
• School of Technology
• Signal Processing and Communications Lab Seminars
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.