Overcomplete Dictionary Design: The Impact of the Sparse Representation Algorithm

The design of dictionaries for sparse representations is typically done by iterating two stages: compute sparse representations for the fixed dictionary and update the dictionary using the fixed representations. Most of the innovation in recent work was proposed for the update stage, while the representation stage was routinely done with Orthogonal Matching Pursuit (OMP), due to its low complexity. We investigate here the use of other greedy sparse representation algorithms, more computationally demanding than OMP but still with convenient complexity. These algorithms include a new proposal, the projection-based Orthogonal Least Squares. It turns out that the effect of using better representation algorithms may be more significant than improving the update stage, sometimes even leveling the performance of different update algorithms. The numerous experimental results presented here suggest which are the best combinations of methods and open new ways of designing and using dictionaries for sparse representations.