New TIP paper accepted

Sparse Approximation Using M-Term Pursuit and Application in Image and Video Coding

Adel Rahmoune, Pierre Vandergheynst, Pascal Frossard

This paper introduces a novel algorithm for sparse approximation in redundant dictionaries, called the M-Term Pursuit (MTP). This algorithm decomposes a signal into a linear combination of atoms that are selected in order to represent the main signal components. The MTP algorithm provides an adaptive representation for signals in any complete dictionary. The basic idea behind the MTP is to partition the dictionary into L quasi-disjoint sub-dictionaries. A k-term signal approximation is then computed iteratively, where each iteration leads to the selection of M ≤ L atoms based on thresholding. The MTP algorithm is shown to achieve competitive performance with the Matching Pursuit (MP) algorithm that greedily selects atoms one by one. This is due to the efficient partitioning of the dictionary. At the same time, the computational complexity is dramatically reduced compared to Matching Pursuit due to the batch selection of atoms. We finally illustrate the performance of MTP in image and video compression applications, where we show that the suboptimal atom selection of MTP is largely compensated by the reduction in complexity compared to MP.