matching pursuit

File:Matching pursuit.png (top) represents an atom (a wavelet centered in time according to the horizontal position and with frequency corresponding to height). The color of the pixel gives the inner product of the corresponding wavelet atom with the signal (bottom). Matching pursuit should represent the signal by just a few atoms, such as the three at the centers of the clearly visible ellipses.]]

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 $D$ . The basic idea is to approximately represent a signal $f$ from Hilbert space $H$ as a weighted sum of finitely many functions $g_{\gamma_n}$ (called atoms) taken from $D$ . An approximation with $N$ atoms has the form

: $f(t) \approx \hat f_N(t) := \sum_{n=1}^{N} a_n g_{\gamma_n}(t)$

where $g_{\gamma_n}$ is the $\gamma_n$ th column of the matrix $D$ and $a_n$ is the scalar weighting factor (amplitude) for the atom $g_{\gamma_n}$ . 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_{N+1}=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{ subject to } \ \|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_{\gamma_n}=a_n$ . 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). 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

File:Orthogonal Matching Pursuit.gif

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{{cite journal | last1 = Mallat | first1 = S. G. | last2 = Zhang | first2 = Z. | year = 1993 | title = Matching Pursuits with Time-Frequency Dictionaries | journal = IEEE Transactions on Signal Processing | volume = 1993 | issue = 12| pages = 3397–3415 | doi = 10.1109/78.258082 | bibcode = 1993ITSP...41.3397M | s2cid = 14427335 }} 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=1}^N$ and indices for corresponding atoms $(\gamma_n)_{n=1}^N$ .

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}$ )

return

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.

Properties

The algorithm converges (i.e. $R_{n}\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_{N+1}\|^2 + \sum_{n=1}^{N}{|a_n|^2}$ .

In the case that the vectors in $D$ are orthonormal, rather than being redundant, then MP is a form of principal component analysis

Applications

Matching pursuit has been applied to signal, image{{cite book | last1 = Perrinet | first1 = L. | chapter = Sparse models for Computer Vision|year= 2015 | chapter-url = https://www.invibe.net/LaurentPerrinet/Publications/Perrinet15bicv | title = Biologically Inspired Computer Vision | volume = 14 | pages = 319–346| doi = 10.1002/9783527680863.ch14 | arxiv = 1701.06859| isbn = 9783527680863 | s2cid = 2085413 }} and video coding,{{cite book | last1 = Bergeaud | first1 = F. | last2 = Mallat | first2 = S. | title = Proceedings., International Conference on Image Processing| chapter = Matching pursuit of images |year= 1995 | volume = 1 | pages = 53–56 | doi = 10.1109/ICIP.1995.529037 | isbn = 978-0-7803-3122-8 | s2cid = 721789 }}{{cite journal | last1 = Neff | first1 = R. | last2 = Zakhor | first2 = A. | author2-link=Avideh Zakhor | year = 1997 | title = Very low bit-rate video coding based on matching pursuits | journal = IEEE Transactions on Circuits and Systems for Video Technology | volume = 7 | issue = 1| pages = 158–171 | doi = 10.1109/76.554427 | s2cid = 15317511 }} shape representation and recognition,{{cite journal | last1 = Mendels | first1 = F. | last2 = Vandergheynst | first2 = P. | last3 = Thiran | first3 = J.P. | year = 2006 | title = Matching pursuit-based shape representation and recognition using scale-space | doi = 10.1002/ima.20078 | journal = International Journal of Imaging Systems and Technology| volume = 16| issue = 5| pages = 162–180| s2cid = 5132416 | url = http://infoscience.epfl.ch/record/101552 }} 3D objects coding,{{cite journal | last1 = Tosic | first1 = I. | last2 = Frossard | first2 = P. | last3 = Vandergheynst | first3 = P. | year = 2005 | title = Progressive coding of 3D objects based on over-complete decompositions | doi = 10.1109/tcsvt.2006.883502 | journal = IEEE Transactions on Circuits and Systems for Video Technology| volume = 16| issue = 11| pages = 1338–1349| s2cid = 3031513 | url = http://infoscience.epfl.ch/record/87305 }} and in interdisciplinary applications like structural health monitoring.{{cite journal | last1 = Chakraborty | first1 = Debejyo | last2 = Kovvali | first2 = Narayan | last3 = Wei | first3 = Jun | last4 = Papandreou-Suppappola | first4 = Antonia | last5 = Cochran | first5 = Douglas | last6 = Chattopadhyay | first6 = Aditi | author6-link = Aditi Chattopadhyay | year = 2009 | title = Damage Classification Structural Health Monitoring in Bolted Structures Using Time-frequency Techniques | journal = Journal of Intelligent Material Systems and Structures | volume = 20 | issue = 11| pages = 1289–1305 | doi = 10.1177/1045389X08100044 | s2cid = 109511712 }} 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.{{cite journal | last1 = Perrinet | first1 = L. U. | last2 = Samuelides | first2 = M. | last3 = Thorpe | first3 = S. | year = 2002 | title = Sparse spike coding in an asynchronous feed-forward multi-layer neural network using Matching Pursuit | url = http://www.incm.cnrs-mrs.fr/LaurentPerrinet/Publications/Perrinet02sparse | journal = Neurocomputing | volume = 57C | pages = 125–34 | doi = 10.1016/j.neucom.2004.01.010 }}{{dead link|date=January 2018 |bot=InternetArchiveBot |fix-attempted=yes }}

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).{{cite journal | last1 = Lin | first1 = Jian-Liang | last2 = Hwang | first2 = Wen-Liang | last3 = Pei | first3 = Soo-Chang | year = 2007 | title = Fast matching pursuit video coding by combining dictionary approximation and atom extraction | journal = IEEE Transactions on Circuits and Systems for Video Technology | volume = 17 | issue = 12| pages = 1679–1689 | doi=10.1109/tcsvt.2007.903120| citeseerx = 10.1.1.671.9670 | s2cid = 8315216 }}

The matching pursuit algorithm is used in MP/SOFT, a method of simulating quantum dynamics.{{cite journal | last1 = Wu | first1 = Yinghua | last2 = Batista | first2 = Victor S. | year = 2003 | title = Matching-pursuit for simulations of quantum processes | doi = 10.1063/1.1560636 | journal = J. Chem. Phys. | volume = 118 | issue = 15| pages = 6720–6724| bibcode = 2003JChPh.118.6720W | s2cid = 37544146 }}

MP is also used in dictionary learning.{{cite journal | last = Perrinet | first = L. P. | year = 2010 | title = Role of homeostasis in learning sparse representations | doi = 10.1162/neco.2010.05-08-795 | pmid = 20235818 | journal = Neural Computation | volume = 22| issue = 7 | pages = 1812–1836| arxiv = 0706.3177 | pmc=2929690}}{{cite journal | last1 = Aharon | first1 = M. |author1-link = Michal Aharon | last2 = Elad | first2 = M. | last3 = Bruckstein | first3 = A.M. | year = 2006 | title = The K-SVD: An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation | doi = 10.1109/tsp.2006.881199 | journal = IEEE Transactions on Signal Processing | volume = 54| issue = 11| pages = 4311–4322| bibcode = 2006ITSP...54.4311A | s2cid = 7477309 }} 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{{cite journal | last1 = Müller | first1 = Ralf R. | last2 = Gäde | first2 = Bernhard | last3 = Bereyhi | first3 = Ali | year = 2021 | title = Linear computation coding | arxiv = 2102.00398 }} to speed-up the computation of matrix-vector products.

Extensions

A popular extension of Matching Pursuit (MP) is its orthogonal version: Orthogonal Matching Pursuit{{cite book | last1 = Pati | first1 = Y. | last2 = Rezaiifar | first2 = R. | last3 = Krishnaprasad | first3 = P. | title = Proceedings of 27th Asilomar Conference on Signals, Systems and Computers | chapter = Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition | year = 1993 | doi = 10.1109/acssc.1993.342465 | pages = 40–44 | isbn = 978-0-8186-4120-6 | citeseerx = 10.1.1.348.5735 | s2cid = 16513805 }}{{cite journal | last1 = Davis | first1 = G. | last2 = Mallat | first2 = S. | last3 = Zhang | first3 = Z. | year = 1994 | title = Adaptive time-frequency decompositions with matching pursuits | doi = 10.1117/12.173207 | journal = Optical Engineering | volume = 33| issue = 7| pages = 2183| bibcode = 1994OptEn..33.2183D }} (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.{{Cite journal|last1=Ding|first1=J.|last2=Chen|first2=L.|last3=Gu|first3=Y.|date=2013|title=Perturbation Analysis of Orthogonal Matching Pursuit|url=https://ieeexplore.ieee.org/document/6320703|journal=IEEE Transactions on Signal Processing|volume=61|issue=2|pages=398–410|doi=10.1109/TSP.2012.2222377|issn=1941-0476|arxiv=1106.3373|bibcode=2013ITSP...61..398D |s2cid=17166658 }} The incremental multi-parameter algorithm (IMP), published three years before MP, works in the same way as OMP.{{Cite book|last1=Mather|first1=John|title=1990 Conference Record Twenty-Fourth Asilomar Conference on Signals, Systems and Computers, 1990 |chapter=The Incremental Multi-Parameter Algorithm |date=1990|chapter-url=https://ieeexplore.ieee.org/document/523362|volume=1 |page=368 |doi=10.1109/ACSSC.1990.523362|isbn=0-8186-2180-X |s2cid=61327933 |issn=1058-6393}}

Extensions such as Multichannel MP"Piecewise linear source separation", R. Gribonval, Proc. SPIE '03, 2003 and Multichannel OMP{{cite journal | last1 = Tropp | first1 = Joel | author-link = Joel Tropp | author-link2 = Anna C. Gilbert | last2 = Gilbert | first2 = A. | last3 = Strauss | first3 = M. | year = 2006 | title = Algorithms for simultaneous sparse approximations; Part I : Greedy pursuit | journal = Signal Proc. – Sparse Approximations in Signal and Image Processing | volume = 86 | issue = 3| pages = 572–588 | doi=10.1016/j.sigpro.2005.05.030| bibcode = 2006SigPr..86..572T }} 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.{{cite book | chapter = Sparse models for Computer Vision | doi = 10.1002/9783527680863.ch14| arxiv =1701.06859| title = Biologically Inspired Computer Vision| pages = 319–346| year = 2015| last1 = Perrinet| first1 = Laurent U.| isbn = 9783527680863| s2cid = 2085413}}

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),{{cite journal | last1 = Tropp | first1 = Joel A. | author-link2 = Anna C. Gilbert | last2 = Gilbert | first2 = Anna C. | year = 2007 | title = Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit | url = http://www.acm.caltech.edu/~jtropp/papers/TG07-Signal-Recovery.pdf | journal = IEEE Transactions on Information Theory | volume = 53 | issue = 12| pages = 4655–4666| doi = 10.1109/tit.2007.909108 | s2cid = 6261304 }} Stagewise OMP (StOMP),{{cite journal | last1 = Donoho | first1 = David L. | last2 = Tsaig | first2 = Yaakov | last3 = Drori | first3 = Iddo | last4 = Jean-luc | first4 = Starck | year = 2006 | title = Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit | doi = 10.1109/tit.2011.2173241 | journal = IEEE Transactions on Information Theory| volume = 58| issue = 2| pages = 1094–1121| s2cid = 7923170 | doi-access = }} compressive sampling matching pursuit (CoSaMP),{{cite journal | last1 = Needell | first1 = D. | last2 = Tropp | first2 = J.A. | year = 2009 | title = CoSaMP: Iterative signal recovery from incomplete and inaccurate samples | doi = 10.1016/j.acha.2008.07.002 | journal = Applied and Computational Harmonic Analysis | volume = 26| issue = 3| pages = 301–321| arxiv = 0803.2392 | s2cid = 1642637 }} Generalized OMP (gOMP),{{Cite journal|last1=Wang|first1=J.|last2=Kwon|first2=S.|last3=Shim|first3=B.|year=2012|title=Generalized Orthogonal Matching Pursuit|journal=IEEE Transactions on Signal Processing|volume=60|issue=12|pages=6202–6216|doi=10.1109/TSP.2012.2218810|bibcode=2012ITSP...60.6202J|arxiv=1111.6664|s2cid=2585677 }} and Multipath Matching Pursuit (MMP).{{cite journal | last1 = Kwon | first1 = S. | last2 = Wang | first2 = J. | last3 = Shim | first3 = B. | year = 2014 | title = Multipath Matching Pursuit | journal = IEEE Transactions on Information Theory | volume = 60 | issue = 5| pages = 2986–3001 | doi = 10.1109/TIT.2014.2310482 | arxiv = 1308.4791 | s2cid = 15134308 }}

References

Category:Multivariate statistics

Category:Signal processing