Rahmoune, Adel
Vandergheynst, Pierre
Frossard, Pascal
Sparse Approximation Using M-Term Pursuit and Application in Image and Video Coding
IEEE Transactions on Image Processing
IEEE Transactions on Image Processing
IEEE Transactions on Image Processing
IEEE Transactions on Image Processing
21
4
LTS4
2012
2012
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 subdictionaries. A k-term signal approximation is then iteratively computed, 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 efficient partitioning of the dictionary. At the same time, the computational complexity is dramatically reduced compared to MP 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 with MP.
Institute of Electrical and Electronics Engineers
1057-7149
IEEE Transactions on Image Processing
Journal Articles
10.1109/TIP.2011.2181525