  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.
