Convex block-sparse linear regression with expanders -- provably
This work addresses the need for efficient sparse matrix methods in machine learning and optimization, offering a convex solution that reduces computational complexity, though it is incremental as it builds on existing non-convex approaches.
The paper tackles the problem of block-sparse recovery from linear measurements using convex optimization with expander matrices, showing that this approach achieves faster recovery times compared to dense matrices while maintaining competitive performance, as supported by experiments on synthetic and real data.
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.