A randomized algorithm for model-based sparse signal recovery

This paper addresses the task of sparse signal recovery that leverages signal structure. Based on the model-based compressive sensing framework, we developed an efficient approximation algorithm for the model-projection problem. This problem is framed as a constrained graph optimization problem, which is NP-hard. To tackle the NP-hard optimization problem, we convert it into a linear programming problem and design a randomized algorithm to obtain an integral solution. The integral solution is optimal in expectation. We demonstrate that the algorithm exhibits the same geometric convergence as previous approaches. It has been tested on various compressing matrices. Our proposed algorithm demonstrates improved recoverability and requires fewer iterations to recover the signal compared to previous methods. Furthermore, we establish that some matrices that are not known to meet the Restricted Isometry Property (RIP) can be scaled to a RIP matrix, and our algorithm maintains the same geometric convergence property with these matrices. The experimental results from these random matrices support our theoretical analysis.