Matching pursuit
Encyclopedia
Matching pursuit is a type of numerical technique which involves finding the "best matching" projections of multidimensional data onto an over-complete dictionary 
. The basic idea is to represent a signal 
from Hilbert space
as a weighted sum of functions 
(called atoms) taken from 
:
An example of similar representation is the Fourier series
expansion where the dictionary is built only from 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
.
By taking an extremely redundant dictionary we can look in it for functions that best match a signal
. Finding a representation where most of the coefficients in the sum are close to 0 (sparse representation
) is desirable for signal coding and compression.
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
and any dictionary 
a sorted list of indexes and scalars which are sub-optimal solution to the problem of sparse signal representation:
Input: Signal:
, dictionary 
.
Output: List of coefficients:
.
Initialization:
;
;
Repeat:
find
with maximum inner product 
;
;
;
;
Until stop condition (for example:
)
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.
{|
|}
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).
on the dictionary 
. In fact, this algorithm solves the sparse problem :
, with 
the 
pseudo-norm equal to the number of nonzero elements of 
.
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), and compressive sampling matching pursuit (CoSAMP).
. The basic idea is to represent a signal from Hilbert spaceHilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
as a weighted sum of functions (called atoms) taken from :An example of similar representation is the Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
expansion where the dictionary is built only from 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
.By taking an extremely redundant dictionary we can look in it for functions that best match a signal
. Finding a representation where most of the coefficients in the sum are close to 0 (sparse representationSparse approximation
Sparse approximation is the problem of finding a signal or vector estimate with sparseness property, that is having a small number of nonzero elements, that satisfies a system of equations....
) is desirable for signal coding and compression.
The algorithm
Searching over an extremely large dictionary for the best matches is computationally unacceptable for practical applications.In 1993 Mallat
Stéphane Mallat
Stéphane G. Mallat made some fundamental contributions to the development of wavelet theory in the late 1980s and early 1990s...
and Zhang proposed a greedy
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
solution that is known from that time as Matching Pursuit.
The algorithm iteratively generates for any signal
and any dictionary a sorted list of indexes and scalars which are sub-optimal solution to the problem of sparse signal representation:Input: Signal:
, dictionary .Output: List of coefficients:
.Initialization:
;;Repeat:
find
with maximum inner product ;;;;Until stop condition (for example:
)The concept of matching pursuit in signal processing is related to statistical projection pursuit
Projection pursuit
Projection pursuit 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 interesting...
, 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
in the space spanned by the dictionary. - For all
the energy conservation equation is satisfied:
{|
|}
- The error
decreases monotonically and its decay is exponential.
Applications
Matching pursuit has already been applied into applications that include 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).
Extensions
The first extension of Matching Pursuit (MP) is its orthogonal version : Orthogonal Matching Pursuit (OMP). The main difference with MP is that coefficients are the orthogonal projection of the signal on the dictionary . In fact, this algorithm solves the sparse problem : , with the pseudo-norm equal to the number of nonzero elements of .Extensions such as Multichannel MP and Multichannel OMP allow to process multicomponents signals.
Matching pursuit is related to the field of compressed sensing
Compressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
and has been extended by researchers in that community. Notable extensions are Orthogonal Matching Pursuit (OMP), Stagewise OMP (StOMP), and compressive sampling matching pursuit (CoSAMP).
See also
- Principal component analysis (PCA)
- Projection pursuitProjection pursuitProjection pursuit 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 interesting...
- Image processingImage processingIn electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
- Signal processingSignal processingSignal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...