Matching pursuit
   HOME

TheInfoList



OR:

Matching pursuit (MP) is a
sparse approximation Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, signa ...
algorithm which finds 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 In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
H as a weighted sum of finitely many functions g_ (called atoms) taken from D. An approximation with N atoms has the form : f(t) \approx \hat f_N(t) := \sum_^ a_n g_(t) where g_ is the \gamma_nth column of the matrix D and a_n is the scalar weighting factor (amplitude) for the atom g_. 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 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 \gamma_N and a_N is denoted by :R_=f-\hat f_N. 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 : \min_x \, f - D x \, _2^2 \ \text \ \, x\, _0 \le N, where \, x\, _0 is 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_=a_n. Solving the sparsity problem exactly is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
, which is why approximation methods like MP are used. For comparison, consider the
Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...
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). The main disadvantage of Fourier analysis in signal processing is that it extracts only the global features of the signals and does not adapt to the analysed signals f. By taking an extremely redundant dictionary, we can look in it for atoms (functions) that best match a signal f.


The algorithm

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 and indices for corresponding atoms (\gamma_n)_^N . Initialization: R_1\,\leftarrow\,f(t); n\,\leftarrow\,1; Repeat: Find g_ \in D with maximum inner product , \langle R_n, g_ \rangle , ; a_n\,\leftarrow\,\langle R_n, g_\rangle ; R_\,\leftarrow\,R_n - a_n g_; n\,\leftarrow\,n + 1; Until stop condition (for example: \, R_n\, < \mathrm ) return In signal processing, the concept of matching pursuit is related to statistical
projection pursuit Projection pursuit (PP) is a type of statistical technique which involves finding the most "interesting" possible projections in multidimensional data. Often, projections which deviate more from a normal distribution are considered to be more inter ...
, in which "interesting" projections are found; ones that deviate more from a
normal distribution In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is : f(x) = \frac e^ The parameter \mu ...
are considered to be more interesting.


Properties

* The algorithm converges (i.e. R_\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_\, ^2 + \sum_^ . * In the case that the vectors in D are orthonormal, rather than being redundant, then MP is a form of
principal component analysis Principal component analysis (PCA) is a popular technique for analyzing large datasets containing a high number of dimensions/features per observation, increasing the interpretability of data while preserving the maximum amount of information, and ...


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 Sparse coding is a representation learning method which aims at finding a sparse representation of the input data (also known as sparse coding) in the form of a linear combination of basic elements as well as those basic elements themselves. These ...
. 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. 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 Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal, by finding solutions to Underdetermined ...
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

* CLEAN algorithm *
Image processing An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
*
Least-squares spectral analysis Least-squares spectral analysis (LSSA) is a method of estimating a frequency spectrum, based on a least squares fit of sinusoids to data samples, similar to Fourier analysis. Fourier analysis, the most used spectral method in science, generally ...
* Principal component analysis (PCA) *
Projection pursuit Projection pursuit (PP) is a type of statistical technique which involves finding the most "interesting" possible projections in multidimensional data. Often, projections which deviate more from a normal distribution are considered to be more inter ...
*
Signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...
*
Sparse approximation Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, signa ...
*
Stepwise regression In statistics, stepwise regression is a method of fitting regression models in which the choice of predictive variables is carried out by an automatic procedure. In each step, a variable is considered for addition to or subtraction from the set of ...


References

{{Reflist Multivariate statistics Signal processing