Matching pursuit

If D contains a large number of vectors, searching for the most sparse representation of f is computationally unacceptable for practical applications. In 1993, Mallat and Zhang proposed a greedy solution that they named "Matching Pursuit." For any signal f and any dictionary D, the algorithm iteratively generates a sorted list of atom indices and weighting scalars, which form the sub-optimal solution to the problem of sparse signal representation. Input: Signal: f(t), dictionary D with normalized columns g_i . Output: List of coefficients (a_n)_{n=1}^N and indices for corresponding atoms (\gamma_n)_{n=1}^N . Initialization: R_1\,\leftarrow\,f(t); n\,\leftarrow\,1; Repeat: Find g_{\gamma_n} \in D with maximum inner product | \langle R_n, g_{\gamma_n} \rangle | ; a_n\,\leftarrow\,\langle R_n, g_{\gamma_n}\rangle ; R_{n+1}\,\leftarrow\,R_n - a_n g_{\gamma_n}; n\,\leftarrow\,n + 1; Until stop condition (for example: \|R_n\| ) return In signal processing, the concept of matching pursuit is related to statistical projection pursuit, in which "interesting" projections are found; ones that deviate more from a normal distribution are considered to be more interesting. == Properties ==

• The algorithm converges (i.e. R_{n}\to 0) for any f that is in the space spanned by the dictionary. • The error \|R_n\| decreases monotonically. • As at each step, the residual is orthogonal to the selected filter, the energy conservation equation is satisfied for each N: :\|f\|^2 = \|R_{N+1}\|^2 + \sum_{n=1}^{N}{|a_n|^2} . • In the case that the vectors in D are orthonormal, rather than being redundant, then MP is a form of principal component analysis == Applications ==

Matching pursuit has been applied to signal, image and video coding, shape representation and recognition, 3D objects coding, and in interdisciplinary applications like structural health monitoring. It has been shown that it performs better than DCT based coding for low bit rates in both efficiency of coding and quality of image. The main problem with matching pursuit is the computational complexity of the encoder. In the basic version of an algorithm, the large dictionary needs to be searched at each iteration. Improvements include the use of approximate dictionary representations and suboptimal ways of choosing the best match at each iteration (atom extraction). The matching pursuit algorithm is used in MP/SOFT, a method of simulating quantum dynamics. MP is also used in dictionary learning. In this algorithm, atoms are learned from a database (in general, natural scenes such as usual images) and not chosen from generic dictionaries. A very recent application of MP is its use in linear computation coding to speed-up the computation of matrix-vector products. == Extensions ==

A popular extension of Matching Pursuit (MP) is its orthogonal version: Orthogonal Matching Pursuit (OMP). The main difference from MP is that after every step, all the coefficients extracted so far are updated, by computing the orthogonal projection of the signal onto the subspace spanned by the set of atoms selected so far. This can lead to results better than standard MP, but requires more computation. OMP was shown to have stability and performance guarantees under certain restricted isometry conditions. The incremental multi-parameter algorithm (IMP), published three years before MP, works in the same way as OMP. Extensions such as Multichannel MP and Multichannel OMP allow one to process multicomponent signals. An obvious extension of Matching Pursuit is over multiple positions and scales, by augmenting the dictionary to be that of a wavelet basis. This can be done efficiently using the convolution operator without changing the core algorithm. Matching pursuit is related to the field of compressed sensing and has been extended by researchers in that community. Notable extensions are Orthogonal Matching Pursuit (OMP), Stagewise OMP (StOMP), compressive sampling matching pursuit (CoSaMP), Generalized OMP (gOMP), and Multipath Matching Pursuit (MMP). == See also ==