Model-based Sketching and Recovery with Expanders

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 re- covering 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.


Editor(s):
Chekuri, Chandra
Published in:
Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1529-1543
Presented at:
ACM-SIAM Symposium on Discrete Algorithms, Portland, Oregon, USA, January 5-7, 2014
Year:
2014
ISBN:
978-1-61197-338-9
Keywords:
Laboratories:




 Record created 2013-07-12, last modified 2018-03-17

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)