  Sparse matrices are favorable objects in machine learning and optimization.
When such matrices are used, in place of dense ones, the overall complexity
requirements in optimization can be significantly reduced in practice, both in
terms of space and run-time. Prompted by this observation, we study a convex
optimization scheme for block-sparse recovery from linear measurements. To
obtain linear sketches, we use expander matrices, i.e., sparse matrices
containing only few non-zeros per column. Hitherto, to the best of our
knowledge, such algorithmic solutions have been only studied from a non-convex
perspective. Our aim here is to theoretically characterize the performance of
convex approaches under such setting.
  Our key novelty is the expression of the recovery error in terms of the
model-based norm, while assuring that solution lives in the model. To achieve
this, we show that sparse model-based matrices satisfy a group version of the
null-space property. Our experimental findings on synthetic and real
applications support our claims for faster recovery in the convex setting -- as
opposed to using dense sensing matrices, while showing a competitive recovery
performance.
