Matching Pursuits with random sequential subdictionaries

Matching Pursuits are a class of greedy algorithms commonly used in signal processing, for solving the sparse approximation problem. They rely on an atom selection step that requires the calculation of numerous projections, which can be computationally costly for large dictionaries and burdens their competitiveness in coding applications. We propose using a non-adaptive random sequence of subdictionaries in the decomposition process, thus parsing a large dictionary in a probabilistic fashion with no additional projection cost nor parameter estimation. A theoretical modeling based on order statistics is provided, along with experimental evidence showing that the novel algorithm can be efficiently used on sparse approximation problems. An application to audio signal compression with multiscale time–frequency dictionaries is presented, along with a discussion of the complexity and practical implementations.

► We reduce the atom selection step of MP to subsets of a large dictionary.
► These subsets vary according to a pre-defined pseudo-random sequence.
► The decomposition span the large dictionary space at reduced complexity.
► The process is non-adaptive and applied to approximation and recovery problems.
► Audio compression using the modified algorithms is investigated with good results.