Efficient backward elimination algorithm for sparse signal representation using overcomplete dictionaries

A sparse representation of a signal, i.e., a representation using a small number of vectors chosen from a dictionary of vectors, is highly desirable in many applications. Here, we extend the backward elimination sparse representation algorithm presented by Reeves (see ibid., vol.6, p.266-68, Oct. 1999) to allow for an overcomplete dictionary and develop recursions for its implementation. In the overcomplete case, the representation error cannot be used as a general criterion for elimination of a dictionary vector and other criteria must be considered. Simulation on a test-case dictionary shows that the performance of the proposed algorithm can improve upon that of forward selection methods.