Harmonic Analysis and Signal Processing Seminar

Structured sparse recovery with sparse random matrices

Bubacarr Bah
AIMS South Africa

Wednesday, April 26, 2017, 3:30pm, WWH 312


Compressed sensing seeks to exploit the redundancy (sparsity) of a signal to under sample the signal significantly. Sparsity is a first order prior information on the signal. In many applications signals exhibit an additional structure beyond sparsity. Exploiting this second order prior information about the signal not only enables further sub-sampling but also improves accuracy of reconstruction. The structured sparsity models we consider are tree-sparsity, block-sparsity and loopless group-sparsity. On the other hand, it has been established that sparse sampling matrices scale better than their dense counterparts but they are more difficult to give provable guarantees on. We considered sparse sampling matrices that are adjacency matrices of lossless expander graphs, and we consequently propose two structured sparse recovery algorithms. A non-convex algorithm that converges linearly with the signal dimension and a convex algorithm that is comparable and sometimes outperforms existing popular algorithms.