Model-based sketching and recovery with expanders
Event details
| Date | 19.02.2014 |
| Hour | 16:15 › 17:15 |
| Speaker |
Dr. Bah BUBACARR, EPFL Bio: Bubacarr received a BSc in Mathematics and Physics from the University of the Gambia in 2004, and an MSc in Mathematical Modeling and Scientific Computing from the University of Oxford, Wolfson College in 2008. He received his PhD in Applied and Computational Mathematics from the University of Edinburgh in 2012, supervised by Prof. Jared Tanner. Currently he is a postdoc with Prof. Volkan Cevher at LIONS, École Polytechnique Fédérale de Lausanne (EPFL), Switzerland. Previously he had been a Graduate Assistant at the University of The Gambia (2004-2007). |
| Location | |
| Category | Conferences - Seminars |
Linear sketching and recovery of sparse vectors with randomly constructed sparse matrices has numerous applications in several areas, including compressive sensing, data stream computing, graph sketching, and combinatorial group testing. This paper considers the same problem with the added twist that the sparse coefficients of the unknown vector exhibit further correlations as determined by a known sparsity model. We prove that exploiting model-based sparsity in recovery provably reduces the sketch size without sacrificing recovery quality. In this context, we present the model-expander iterative hard thresholding algorithm for recovering model sparse signals from linear sketches obtained via sparse adjacency matrices of expander graphs with rigorous performance guarantees. The main computational cost of our algorithm depends on the difficulty of projecting onto the model-sparse set. For the tree and group-based sparsity models we describe in this paper, such projections can be obtained in linear time. Finally, we provide numerical experiments to illustrate the theoretical results in action.
Links
Practical information
- Informed public
- Free
Organizer
- Prof. Marco PICASSO
Contact
- Prof. Marco PICASSO