Matching pursuit
Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary
Instead, matching pursuit chooses the atoms one at a time in order to maximally (greedily) reduce the approximation error.
This is achieved by finding the atom that has the highest inner product with the signal (assuming the atoms are normalized), subtracting from the signal an approximation that uses only that one atom, and repeating the process until the signal is satisfactorily decomposed, i.e., the norm of the residual is small, where the residual after calculating
converges quickly to zero, then only a few atoms are needed to get a good approximation to
Such sparse representations are desirable for signal coding and compression.
More precisely, the sparsity problem that matching pursuit is intended to approximately solve is where
Solving the sparsity problem exactly is NP-hard, which is why approximation methods like MP are used.
For comparison, consider the Fourier transform representation of a signal - this can be described using the terms given above, where the dictionary is built from sinusoidal basis functions (the smallest possible complete dictionary).
By taking an extremely redundant dictionary, we can look in it for atoms (functions) that best match a signal
In 1993, Mallat and Zhang[1] proposed a greedy solution that they named "Matching Pursuit."
, 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.
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.
Matching pursuit has been applied to signal, image[2] and video coding,[3][4] shape representation and recognition,[5] 3D objects coding,[6] and in interdisciplinary applications like structural health monitoring.
[8] 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).
[9] The matching pursuit algorithm is used in MP/SOFT, a method of simulating quantum dynamics.
[11][12] In this algorithm, atoms are learned from a database (in general, natural scenes such as usual images) and not chosen from generic dictionaries.
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.
[16] The incremental multi-parameter algorithm (IMP), published three years before MP, works in the same way as OMP.
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.
[20] Matching pursuit is related to the field of compressed sensing and has been extended by researchers in that community.
