An efficient implementation of the backward greedy algorithm for sparse signal reconstruction

Recent work in sparse signal reconstruction has shown that the backward gre edy algorithm can select the optimal subset of unknowns if the perturbation of the data is sufficiently small. We propose an efficient implementation of the backward greedy algorithm that yields a significant improvement in c omputational efficiency over the standard implementation. Furthermore, we p ropose an efficient algorithm for the case in which the transform matrix is too large to be stored. We analyze the computational complexity and compar e the algorithms, and we illustrate the improved efficiency with examples.