Time: Tuesday, September 29, 2015
2:00pm
MTH1311

Speaker: Dr. Bubacarr Bah (University of Texas)

Title: Structured sparse recovery with sparse sampling matrices

Abstract: Compressed sensing seeks to exploit the simplicity (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. On the other hand, a lot of the sampling matrices, for which we are able to prove optimal recovery guarantees, are dense and hence do not scale well with the dimension of the signal. Sparse matrices scale better than their dense counterparts but they are more difficult to give provable guarantees on. The sparse sampling operators we consider are adjacency matrices of lossless expander graphs. They are non-mean zero and they reflect more some of the applications of compressed sensing like the single pixel camera. We also propose a non-convex algorithm that converges linearly with the signal dimension and a convex algorithm that is comparable and sometimes outperforms existing popular algorithms. We also derived sharp sample complexity bounds. This talk will be about these results.