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.