The ReMBo algorithm: Accelerated recovery of jointly sparse vectors

We address the problem of recovering a sparse solution of a linear under-determined system. Two variants of this problem are studied in the literature. One is the case of a sparse vector with only a few non-zero entries, and the other is of a sparse matrix with few rows non-identically zero. In either scenario, the recovery is known to be a difficult combinatorial procedure. In this paper, we develop a method that transforms the recovery of a sparse matrix into the vector formulation. Our method is exact as it allows to infer the sparse matrix from a single sparse solution vector. Once reduced to this basic form, known sub-optimal methods can be employed to approximate the solution. In order to further improve the performance, we derive a prototype algorithm, called ReMBo, that combines a boosting approach together with the reduction process. The boosting stage empirically improves the recovery rate of any given sub-optimal method. Numerical experiments demonstrate the superior performance of ReMBo-based methods in comparison with popular algorithms in terms of run time and empirical recovery rate when tested on random data.