 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Matching pursuit

Article Id: WHEBN0005534001
Reproduction Date:

 Title: Matching pursuit Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Matching pursuit

Matching pursuit

is a type of sparse approximation which involves finding the "best matching" projections of multidimensional data onto an over-complete dictionary D. The basic idea is to represent a signal f from Hilbert space H as a weighted sum of functions g_{\gamma_n} (called atoms) taken from D:

f(t) = \sum_{n=0}^{+\infty} a_n g_{\gamma_n}(t)

where n indexes the atoms that have been chosen, and a_n a weighting factor (an amplitude) for each atom. Given a fixed dictionary, matching pursuit will first find the one atom that has the biggest inner product with the signal, then subtract the contribution due to that atom, and repeat the process until the signal is satisfactorily decomposed.

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. Finding a representation where most of the coefficients in the sum are close to 0 (sparse representation) is desirable for signal coding and compression.

## Contents

• The algorithm 1
• Properties 2
• Applications 3
• Extensions 4
• See also 5
• References 6

## The algorithm

Searching over an extremely large dictionary for the best matches is computationally unacceptable for practical applications. In 1993 Mallat and Zhang proposed a greedy solution that is known from that time as Matching Pursuit. The algorithm iteratively generates for any signal f and any dictionary D a sorted list of indexes and scalars which are the sub-optimal solution to the problem of sparse signal representation. The residual after calculating \gamma_n and a_n is denoted by R_{n+1}.

Algorithm Matching Pursuit
Input: Signal: f(t), dictionary D.
Output: List of coefficients:  \left( a_n, g_{\gamma_n}\right) .
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\| < \mathrm{threshold} )

• "←" is a shorthand for "changes to". For instance, "largestitem" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the value that follows.

The concept of matching pursuit in signal processing is related to statistical projection pursuit, in which "interesting" projections were found; ones that deviate more from a normal distribution are considered to be more interesting.

## Properties

• The algorithm converges for any f in the space spanned by the dictionary.
• For all m the energy conservation equation is satisfied:
\|f\|^2 = \sum_{n=0}^{m-1}{|a_n|^2} + \|R_m\|^2
• The error \|R_n\| decreases monotonically and its decay is exponential.

## 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 has 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 also used in dictionary learning. In this algorithm, atoms are learned from a database and not chosen among generic dictionaries.

The Matching Pursuit algorithm is used in MP/SOFT, a method of simulating quantum dynamics.

## 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 set of atoms selected so far. This can lead to better results than standard MP, but requires more computation.

In fact, this algorithm approximates the sparse problem :

\min_x \| f - D x \|_2^2 \ \text{ subject to } \ \|x\|_0 \le N,

with \|x\|_0 the L_0 pseudo-norm (i.e. the number of nonzero elements of x).

Extensions such as Multichannel MP and Multichannel OMP allow to process multicomponents signals.

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), and Multipath Matching Pursuit (MMP).

## See also

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.