Matching pursuit

Matching pursuit (MP) is a sparse approximation algorithm which involves finding the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary D . The basic idea is to approximately represent a signal f from Hilbert space H as a weighted sum of finitely many functions g γ n (called atoms) taken from D . An approximation with N atoms has the form

Contents

• The algorithm
• Properties
• Applications
• Extensions
• References

where a n is the scalar weighting factor (amplitude) for the atom g γ n ∈ D . Normally, not every atom in D will be used in this sum. 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 biggest 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 γ N and a N is denoted by

If R n converges quickly to zero, then only a few atoms are needed to get a good approximation to f . Such sparse representations are desirable for signal coding and compression. More precisely, the sparsity problem that matching pursuit is intended to approximately solve is

with ∥ x ∥ 0 the L 0 pseudo-norm (i.e. the number of nonzero elements of x ). In the previous notation, the nonzero entries of x are x γ n = a n , and the γ n th column of the matrix D is g γ n . Solving the sparsity problem exactly is NP-hard, which is why approximation methods like MP are used.

For comparison, consider the Fourier series representation of a signal - this can be described in the terms given above, where the dictionary is built from sinusoidal basis functions (the smallest possible complete dictionary). The main disadvantage of Fourier analysis in signal processing is that it extracts only global features of signals and does not adapt to analysed signals f . By taking an extremely redundant dictionary we can look in it for functions that best match a signal f .